[c-nsp] cisco regex puzzle of the day

[Mack McBride]

The junos expression in question DOES NOT involve backtracking.
After a match there is no need to backtrack.

The expression in question goes character by character excluding the 64500.
Note the last part matches 6 digit ASNs that start with 64500.

Mack McBride | Network Architect | ViaWest, Inc.
O: 720.891.2502 | mack.mcbride at viawest.com | www.viawest.com | LinkedIn | Twitter | YouTube



-----Original Message-----
From: cisco-nsp [mailto:cisco-nsp-bounces at puck.nether.net] On Behalf Of Saku Ytti
Sent: Wednesday, March 11, 2015 11:54 AM
To: cisco-nsp at puck.nether.net
Subject: Re: [c-nsp] cisco regex puzzle of the day

On (2015-03-11 17:28 +0000), Mack McBride wrote:

Hey,

> There is no back tracking in the junos regex nor would backtracking really help.
> Doing this is complicated on cisco due to the lack of negating a full as.

There definitely is backtracking, the reason (64500_)+.+ doesn't work, and matches 64500 64500 is that after the (64500_)+ has chomped up both of them, it backtracks, trying to see if by going back, it can further satisfy the .+, and it'll notice that by going back whole 64500 it can satisfy both.

If it wouldn't backtrack, '64500 64500' wouldn't match, but 64500 64501 would match, and we would in simple and clear regexp achieve what we want.

However, disabling backtracking globally would break common use-case such as ^.*_64500$

Turns out, some regexp engines allow turning off backtracking conditionally either by adding '+' after +*, or by adding ?> to group. In which case (64500_)++.+ and (?>64500_)+.+ would work.
Unfortunately neither regexp engine IOS has supports either of these.


> I haven't tested this but it should work:
>
> (65400_)+([1-57-9][0-9]*_|6[01-35-9][0-9]*_|64[01-46-9][0-9]*_|645[1-9
> ][0-9]*_|6450[1-9][0-9]*_|64500[0-9]+_)+

Thanks, I was afraid it'll be something terrible, I don't dare to try  :)

--
  ++ytti
_______________________________________________
cisco-nsp mailing list  cisco-nsp at puck.nether.net https://puck.nether.net/mailman/listinfo/cisco-nsp
archive at http://puck.nether.net/pipermail/cisco-nsp/
This message contains information that may be confidential, privileged or otherwise protected by law from disclosure. It is intended for the exclusive use of the addressee(s). Unless you are the addressee or authorized agent of the addressee, you may not review, copy, distribute or disclose to anyone the message or any information contained within. If you have received this message in error, please contact the sender by electronic reply and immediately delete all copies of the message.