New RE_PROBE_IPV6_ONLY with better complexity in worst case

kellyjonbrazil / jc

CLI tool and python library that converts the output of popular command-line tools, file-types, and common strings to JSON, YAML, or Dictionaries. This allows piping of output to tools like jq and simplifying automation scripts.

MIT License

7.92k stars 210 forks source link

New RE_PROBE_IPV6_ONLY with better complexity in worst case #609

Closed AlekseyLobanov closed 3 days ago

AlekseyLobanov commented 1 month ago

I found that RE_PROBE_IPV6_ONLY may have awful complexity (exponential) on some cases like ':'*100.

Fix included, tests are green.

AlekseyLobanov commented 1 month ago

Also three Regular Expressions may have cubic (N^3) complexity on some examples and I unable to perform quick fix. What do you think about using RE2 library? It is still really fast but also will be fast on this examples.

AlekseyLobanov commented 1 month ago

As a POC I tried

traceroute6 to turner-tls.map.fastly.net (2a04:4e42:200::323) from 2600:1700:bab0:d40:985:f00a:98bd:f142, 5 hops max, 12 byte packets
 1  * * *
 2  :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::  27.635 ms  20.383 ms  23.438 ms
 3  * * *
 4  2001:1890:ff:ff08:12:242:117:16  20.118 ms  20.327 ms  21.213 ms
 5  * * *

at the web demo

kellyjonbrazil commented 3 days ago

Thanks for this fix! I don't want to introduce any new dependencies, so we'll have to pass on RE2.