Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
How to do regexp analysis
Search
Iskander (Alex) Sharipov
April 25, 2020
Programming
0
300
How to do regexp analysis
Iskander (Alex) Sharipov
April 25, 2020
Tweet
Share
More Decks by Iskander (Alex) Sharipov
See All by Iskander (Alex) Sharipov
quasigo
quasilyte
0
61
Go gamedev: XM music
quasilyte
0
120
Zero alloc pathfinding
quasilyte
0
510
Mycelium
quasilyte
0
66
Roboden game pitch
quasilyte
0
210
Ebitengine Ecosystem Overview
quasilyte
1
900
Go gamedev patterns
quasilyte
0
480
profile-guided code analysis
quasilyte
0
360
Go inlining
quasilyte
0
120
Other Decks in Programming
See All in Programming
CSC305 Lecture 08
javiergs
PRO
0
280
AIと人間の共創開発!OSSで試行錯誤した開発スタイル
mae616
2
810
alien-signals と自作 OSS で実現する フレームワーク非依存な ロジック共通化の探求 / Exploring Framework-Agnostic Logic Sharing with alien-signals and Custom OSS
aoseyuu
2
660
組込みだけじゃない!TinyGo で始める無料クラウド開発入門
otakakot
2
380
Vueのバリデーション、結局どれを選べばいい? ― 自作バリデーションの限界と、脱却までの道のり ― / Which Vue Validation Library Should We Really Use? The Limits of Self-Made Validation and How I Finally Moved On
neginasu
2
1.6k
TFLintカスタムプラグインで始める Terraformコード品質管理
bells17
2
450
コード生成なしでモック処理を実現!ovechkin-dm/mockioで学ぶメタプログラミング
qualiarts
0
270
Goで実践するドメイン駆動開発 AIと歩み始めた新規プロダクト開発の現在地
imkaoru
4
900
デミカツ切り抜きで面倒くさいことはPythonにやらせよう
aokswork3
0
260
スマホから Youtube Shortsを見られないようにする
lemolatoon
27
34k
Cursorハンズオン実践!
eltociear
2
1.2k
AkarengaLT vol.38
hashimoto_kei
1
120
Featured
See All Featured
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
130k
Side Projects
sachag
455
43k
Fireside Chat
paigeccino
41
3.7k
KATA
mclloyd
PRO
32
15k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
23
1.5k
A better future with KSS
kneath
239
18k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
116
20k
Build The Right Thing And Hit Your Dates
maggiecrowley
38
2.9k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Designing for humans not robots
tammielis
254
26k
Git: the NoSQL Database
bkeepers
PRO
431
66k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
52
5.7k
Transcript
How to do regexp analysis @quasilyte / GolangKazan 2020
Not why, but how Implementation advice and potential issues overview.
go-critic NoVerify Open-Source analyzers
Discussion plan • Handling regexp syntax • Analyzing regexp flow
• Finding bugs in regular expressions • Regexp rewriting
Handling regexp syntax
Why making own parser? Most regexp libraries use parsers that
give up on the first error. For analysis, we need rich AST (parse tree even) and error-tolerant parser.
Writing a parser Useful resources: • Regexp syntax docs (BNF,
re2-syntax) • Pratt parsers tutorial (RU, EN) • Regexp corpus for tests (gist) • Dialect-specific documentation
Composition operators Only two: • Concatenation: xy (“x” followed by
“y”) • Alternation: x|y (“x” or “y”) Concatenation is implicit. And we want it to be explicit in AST.
Concat operation `0|xy[a-z]` ⬇ 0 | x ⋅ y ⋅
[a-z]
Parsing concatenation • Insert concat tokens • Parse regexp like
it has explicit concat xy? ⬇ “x” “⋅” “y” “?”
Char classes (are hard) • Different escaping rules • Char-ranges
can be tricky This is char range: [\n-\r] 4 chars This is not: [\d-\r] \d, “-” and “\r”
Char classes syntax `[][]` What is it?
Char classes syntax `[][]` A char class of “]” and
“[“! `[\]\[]`
Char classes syntax `[^]*|\[[^\]]` What is it?
Char classes syntax `[^]*|\[[^\]]` A single char class! `[^\]*|\[\[^\]]`
Char classes syntax `[+=-_]` What will be matched?
Char classes syntax `[+=-_]` “F” matched
Char classes syntax `[+=\-_]` “F” not matched
Chars and literals • Consecutive “chars” can be merged •
Single char should not be converted Both forms (with and without merge) are useful. Merged chars simplify literal substring analysis.
Concat operation `foox?y` ⬇ lit(foo) ⋅ ?(char(x)) ⋅ char(y)
AST types There are at least two approaches: • One
type + enum tags • Many types + shared interface/base Both have pros and cons.
AST types type Expr struct { Kind ExprKind // enum
tag Value string // source text Args []Expr // sub-expr list } type ExprKind int
AST types const ( ExprNone ExprKind = iota ExprChar ExprLiteral
// list of chars ExprConcat // xy ExprAlt // x|y // etc. )
Helper for the next slide func charExpr(val string) Expr {
return Expr{ Kind: ExprChar, Value: val, } }
AST of `x|yz` Expr{ Kind: ExprAlt, Value: "x|yz", Args: []Expr{
charExpr("x"), { Kind: ExprConcat, Value: "yz", Args: []Expr{ charExpr("y"), charExpr("z"), }, }, }, }
Go regexp parsing library https://github.com/quasilyte/regex contains a `regex/syntax` package that
is used in both NoVerify and go-critic. It can parse both re2 and pcre patterns.
Analyzing regexp flow
Regexp flags A regular expression can have an initial set
of flags, then it can add or remove any of them inside the expression. The effect is localized to the current (potentially capturing) group.
Concat operation `/((?i)a(?m)b(?-m)c)d/s` ^--------- flags: si Entered a group with
“i” flag
Concat operation `/((?i)a(?m)b(?-m)c)d/s` -^ flags: sim Mid-group flags: add “m”
Concat operation `/((?i)a(?m)b(?-m)c)d/s` -------------^ flags: si Mid-group flags: clear “m”
Concat operation `/((?i)a(?m)b(?-m)c)d/s` -----------------^ flags: s Left a group with
“i” flag
Flags flow • Flags are lexically scoped • Groups are
a scoping unit • Leaving a group drops a scope • Entering a group adds a scope
Back references • Rules vary among engines/dialects • Syntax may
clash with octal literals • Can also be relative/named: \g{-1}, etc We’ll use PHP rules as an example.
Back reference QUIZ! (PHP) \0 ??? \1 … \9 ???
\10 … \77 ???
Back reference QUIZ! (PHP) \0 Octal literal \1 … \9
??? \10 … \77 ???
Back reference QUIZ! (PHP) \0 Octal literal \1 … \9
Back reference \10 … \77 ???
Back reference QUIZ! (PHP) \0 Octal literal \1 … \9
Back reference \10 … \77 It depends!
Groups flow • Capturing groups are numbered from left to
right. • Non-capturing groups are ignored. • Groups can have a name.
Finding bugs in regular expressions
“^” anchor diagnostic Let’s check that “^” is used only
in the beginning position of the pattern. Because if it follows a non-empty match, it’ll never succeed.
Correct “^” usages `^foo` `^a|^b` `a|(b|^c)`
Incorrect “^” usages `foo^` `a^b` `(a|b)^c`
Algorithm • Traverse all starting branches • Mark all reached
“^” as “good” Then traverse a pattern AST normally and report any “^” that was not marked.
The starting branches? • For every “concat” met, it’s the
first element (applied recursively). • If root regexp element is not “concat”, consider it to be a concat of 1 element.
URL matching `google.com`
URL matching `google.com` http://googleocom.ru
URL matching `google.com` http://googleocom.ru http://a.github.io/google.com
URL matching `google\.com` http://googleocom.ru http://a.github.io/google.com
URL matching `^https?://google\.com/` http://googleocom.ru http://a.github.io/google.com
URL matching When “.” is used before common domain name
like “com”, it’s probably a mistake. If we have char sequences represented as a single AST node, this analysis is trivial.
Handling unescaped dot `google.com` lit(google) ⋅ . ⋅ lit(com) Warn
if “.” is followed by a lit with domain name value.
Regexp rewriting
Regexp input generation It’s quite simple to generate a string
that will be matched by a regular expression if you have that regexp AST.
Generating matching string (N=2) `\w*[0-9]?$` *(\w) ⋅ ?([0-9]) ⋅ $
Generating matching string (N=2) `\w*[0-9]?$` *(\w) ⋅ ?([0-9]) ⋅ $
aa N matches of \w
Generating matching string (N=2) `\w*[0-9]?$` *(\w) ⋅ ?([0-9]) ⋅ $
aa7 1 match of [0-9]
Generating matching string (N=2) `\w*[0-9]?$` *(\w) ⋅ ?([0-9]) ⋅ $
aa7 May do nothing for $
Regexp input generation Generating a non-matching strings can be useful
for catastrophic backtracking evaluation.
Regexp simplification Instead of writing a matching characters we can
write the pattern syntax itself. By replacing recognized AST node sequences with something simpler, we can perform a regexp simplification.
Regexp simplification `\dxx*` \d ⋅ x ⋅ *(x)
Regexp simplification `\dxx*` \d ⋅ x ⋅ *(x) \d Can’t
simplify \d, write as is
Regexp simplification `\dxx*` \d ⋅ x ⋅ *(x) \dx+ xx*
-> x+
Oh, the possibilities! x{1,} -> x+ [a-z\d][a-z\d] -> [a-z\d]{2} [^\d]
-> \D a|b|c -> [abc]
https://quasilyte.dev/regexp-lint/ Online Demo
Submit your ideas! :) If you have a particular regexp
simplification or bug pattern that is not detected by regexp-lint, let me know.
Thank you.