Upgrade to Pro — share decks privately, control downloads, hide ads and more …

PHP code->rules

PHP code->rules

Iskander (Alex) Sharipov

October 24, 2020
Tweet

More Decks by Iskander (Alex) Sharipov

Other Decks in Programming

Transcript

  1. $x ? true : false Find all ternary expressions that

    could be replaced by just $x 4.7s / 6kk SLOC / 56 Cores
  2. $_ == null null == $_ Find all non-strict comparisons

    with null 4.5s / 6kk SLOC / 56 Cores
  3. for ($_ == $_; $_; $_) $_ Find for loops

    where == is used instead of = inside init clause 4.6s / 6kk SLOC / 56 Cores
  4. • A brief phpgrep history • NoVerify dynamic rules •

    AST pattern matching Main topics for today
  5. • A brief phpgrep history • NoVerify dynamic rules •

    AST pattern matching • Running rules efficiently Main topics for today
  6. • A brief phpgrep history • NoVerify dynamic rules •

    AST pattern matching • Running rules efficiently • Dynamic rules pros & cons Main topics for today
  7. • Types info (NoVerify type inference) • Efficient multi-pattern execution

    • Logical pattern grouping Dynamic rules vs phpgrep
  8. • Types info (NoVerify type inference) • Efficient multi-pattern execution

    • Logical pattern grouping • Documentation mechanisms Dynamic rules vs phpgrep
  9. Dynamic rule example function ternarySimplify() { /** @warning rewrite as

    $x ?: $y */ $x ? $x : $y; } Dynamic rules group name
  10. Is this transformation safe? f() ? f() : 0 =>

    f() ?: 0 Only if f() is free of side effects
  11. Dynamic rule example (extended) function ternarySimplify() { /** * @warning

    rewrite as $x ?: $y * @pure $x */ $x ? $x : $y; }
  12. Dynamic rule example (extended) function ternarySimplify() { /** * @warning

    rewrite as $x ?: $y * @pure $x */ $x ? $x : $y; } $x should be side effect free
  13. Dynamic rule example (extended) function ternarySimplify() { /** * @warning

    rewrite as $x ?: $y * @pure $x * @fix $x ?: $y */ $x ? $x : $y; } auto fix action for NoVerify
  14. Dynamic rule example (@comment) /** * @comment Find ternary expr

    that can be simplified * @before $x ? $x : $y * @after $x ?: $y */ function ternarySimplify() { // ...as before } Dynamic rule documentation
  15. function argsOrder() { /** @warning suspicious args order */ any:

    { str_replace($_, $_, ${"char"}, ${"*"}); str_replace($_, $_, "", ${"*"}); } }
  16. function argsOrder() { /** @warning suspicious args order */ any:

    { str_replace($_, $_, ${"char"}, ${"*"}); str_replace($_, $_, "", ${"*"}); } } “any” pattern grouping
  17. function bitwiseOps() { /** * @warning maybe && is intended?

    * @fix $x && $y * @type bool $x * @type bool $y */ $x & $y; }
  18. function bitwiseOps() { /** * @warning maybe && is intended?

    * @fix $x && $y * @type bool $x * @type bool $y */ $x & $y; } Type filters
  19. T T typed expression object Arbitrary object type T[] Array

    of T-typed elements !T Any type except T !(A|B) Any type except A and B ?T Same as (T|null) Type matching examples
  20. function stringCmp() { /** * @warning compare strings with ===

    * @fix $x === $y * @type string $x * @or * @type string $y */ $x == $y; }
  21. function stringCmp() { /** * @warning compare strings with ===

    * @fix $x === $y * @type string $x * @or * @type string $y */ $x == $y; } Or-connected constraints
  22. 1. Create a rules file 2. Run NoVerify with -rules

    flag How to run custom rules $ noverify -rules rules.php target
  23. function match(Node $pat, Node $n) $pat is a compiled pattern

    $n is a node being matched Matching AST
  24. • Both $pat and $n are traversed • Non-meta nodes

    are compared normally • $pat meta nodes are separate cases • Named matches are collected (capture) Algorithm
  25. • $x is a simple “match any” named match •

    $_ is a “match any” unnamed match • ${"str"} matches string literals • ${"str:x"} is a capturing form of ${"str"} • ${"*"} matches zero or more nodes Valid PHP Syntax! Meta node examples
  26. Pattern matching = $x $x = $a 10 Pattern $x=$x

    Target $a=10 $x is bound to $a
  27. Pattern matching = $x $x = $a $a Pattern $x=$x

    Target $a=$a $x is bound to $a
  28. Pattern matching = $x $x = $a $a Pattern $x=$x

    Target $a=$a $a = $a, pattern matched
  29. Stack-based matching = $a $a Pattern $x=$x Target $a=$a Instructions

    Stack <Assign> $a <NamedAny x> $a <NamedAny x>
  30. Stack-based matching = $a $a Pattern $x=$x Target $a=$a Instructions

    Stack <Assign> $a <NamedAny x> <NamedAny x>
  31. • 2-4 times faster matching • No AST types dependency

    • More optimization opportunities Stack-based matching
  32. Imagine that we have a lot of rules... rule-1 ...

    rule-N PHP file PHP file N * M problem
  33. • AST is traversed only once • For every node,

    run only relevant rules We can tune the matching engine to work very fast N*M cure: categorized rules
  34. • Local: run rules only inside functions • Root: run

    rules only inside global scope • Universal: run rules everywhere Extra registry layer: scopes
  35. rule PHP file ... Assign rule ... TernaryExpr Global scope

    rule ... Assign rule ... TernaryExpr Local scope
  36. rule PHP file ... Assign rule ... TernaryExpr Global scope

    rule ... Assign rule ... TernaryExpr Local scope Scoped group
  37. • Expression can’t contain a statement • Some statements are

    top-level only We don’t use this knowledge right now. Extra registry layer: expr vs stmt
  38. If any rule from a group matched, all other rules

    inside the group are skipped for the current node. • Helps to avoid matching conflicts • Improves performance Group cutoff
  39. // input: $a[0] = $a[0] + 1 function assignOp() {

    /** @fix ++$x */ $x = $x + 1; /** @fix $x += $y */ $x = $x + $y; }
  40. // input: $a[0] = $a[0] + 1 function assignOp() {

    /** @fix ++$x */ $x = $x + 1; /** @fix $x += $y */ $x = $x + $y; } Matched, ++$a[0] suggested
  41. // input: $a[0] = $a[0] + 1 function assignOp() {

    /** @fix ++$x */ $x = $x + 1; /** @fix $x += $y */ $x = $x + $y; } Skipped
  42. • No need to re-compile NoVerify • Simple things are

    simple • No Go coding required Dynamic rules advantages
  43. • No need to re-compile NoVerify • Simple things are

    simple • No Go coding required • Rules are declarative Dynamic rules advantages
  44. • No need to re-compile NoVerify • Simple things are

    simple • No Go coding required • Rules are declarative • No need to know linter internals Dynamic rules advantages
  45. • Not very composable • Too verbose for non-trivial cases

    • Hard to get the autocompletion working PHPDoc-based attributes
  46. • Hard to express flow-based rules • PHP syntax limitations

    • Recursive block search is problematic AST pattern limitations
  47. • NoVerify - static analyzer (linter) • phpgrep - structural

    PHP search • phpgrep VS Code extension • Dynamic rules example • Dynamic rules for static analysis article • Ruleguard - dynamic rules for Go Links