# String.scan hangs in some cases?

**URL:** <https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186>\
**Category:** Ruby\
**Created:** [May 24, 2006, 2:29am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186 "2006-05-24T02:29:49Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 2:29am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/1 "2006-05-24T02:29:49Z")

</div>

Has anyone ever see a call to String.scan (the “regular” form, not the  
block form) just hang when processing a string?

If so, any insight into how that might happen?

Thanks,  
Wes

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 2:43am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/2 "2006-05-24T02:43:39Z")

</div>

Wes G. wrote:

> Has anyone ever see a call to String.scan (the “regular” form, not the  
> block form) just hang when processing a string?
> 
> If so, any insight into how that might happen?
> 
> Thanks,  
> Wes

Got an example you can share that demonstrates the problem?

Maybe the string is huge? Maybe there’s a recursive lookup happening of  
some kind? Dunno without more detail.

Regards,

Dan

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 2:59am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/3 "2006-05-24T02:59:08Z")

</div>

From: “Daniel B.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)

> Got an example you can share that demonstrates the problem?
> 
> Maybe the string is huge? Maybe there’s a recursive lookup happening of  
> some kind? Dunno without more detail.

I’m guessing exponential backtracking when the expression doesn’t match.

For ex:

x = “x” \* 1000  
x \<\< “ab”  
x =~ /x_x_a/ # matches quickly  
x =~ /x_x_b/ # “hangs” trying exponential combinations with  
backtracking

Regards,

Bill

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 10:16am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/4 "2006-05-24T10:16:20Z")

</div>

From: “Robert K.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)

> Yes, that’s a property of NFA based regular expression engines. Some  
> patterns have awful runtime characteristics because of the  
> backtracking. Without looking too close at your patter I guess in  
> this case it’s caused by having “x\*” twice in your RX - not very  
> useful anyway.

Thanks 🙂 We haven’t seen the OP’s regexp yet; I was just  
offering the above as an example of what can cause the  
hanging he described.

Regards,

Bill

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 9:12am UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/5 "2006-05-24T09:12:30Z")

</div>

2006/5/24, Bill K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> > 
> 
> x \<\< “ab”  
> x =~ /x_x_a/ # matches quickly  
> x =~ /x_x_b/ # “hangs” trying exponential combinations with backtracking

Yes, that’s a property of NFA based regular expression engines. Some  
patterns have awful runtime characteristics because of the  
backtracking. Without looking too close at your patter I guess in  
this case it’s caused by having “x\*” twice in your RX - not very  
useful anyway. If you are interested in more detail I recommend  
reading “Mastering Regular Expressions”:

> **[Mastering Regular Expressions: Friedl, Jeffrey: 9780596528126: Amazon.com: Books](https://www.amazon.com/Mastering-Regular-Expressions-Jeffrey-Friedl/dp/0596528124)**
>
> Mastering Regular Expressions \[Friedl, Jeffrey\] on Amazon.com. \*FREE\* shipping on qualifying offers. Mastering Regular Expressions

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 5:11pm UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/6 "2006-05-24T17:11:09Z")

</div>

Just for kicks, here was the original regex - attempting to match  
against a string containing an entire HTML page OR a style sheet.

/(?=\<style)_?background._?(?=-image)_?:._?url((._?))._?(?=\</style\>)\*?/

I was attempting to make the \<style and parts optional.

As it turns out, there are so many different ways that a style can be  
specified in a HTML page, that I just went with the much simpler:

/background._?:._?url((.\*?))/i

Wes

---

<div class="post-metadata">

**Author:** ![weyus](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/w/7ab992/32.png) [@weyus](https://www.ruby-forum.com/u/weyus)\
**Post date:** [May 24, 2006, 5:03pm UTC](https://www.ruby-forum.com/t/string-scan-hangs-in-some-cases/95186/7 "2006-05-24T17:03:42Z")

</div>

Bill K. wrote:

> From: “Robert K.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)
> 
> > Yes, that’s a property of NFA based regular expression engines. Some  
> > patterns have awful runtime characteristics because of the  
> > backtracking. Without looking too close at your patter I guess in  
> > this case it’s caused by having “x\*” twice in your RX - not very  
> > useful anyway.
> 
> Thanks 🙂 We haven’t seen the OP’s regexp yet; I was just  
> offering the above as an example of what can cause the  
> hanging he described.
> 
> Regards,
> 
> Bill

All,

Thanks for giving me some idea of what might be wrong. For now, I’ve  
gone with a simpler regex that I think will work fine. My original  
pattern was attempting to allow several portions of the pattern to be  
optional and the more that I think about it, the more it makes sense  
that this might occur.

I will keep (?\>pattern) in mind as a way to inhibit backtracking.

Thanks,  
Wes