3v4l.org

run code in 300+ PHP versions simultaneously
<?php class Element { const TYPE_LITERAL = 0; const TYPE_GROUP = 1; const END_OF_STRING = 2; public $type; public $value; public $next = self::END_OF_STRING; } function buildGraph($tokens) { $root = new Element; $root->type = Element::TYPE_GROUP; while ( $tokens->valid() ) { $token = $tokens->current(); $tokens->next(); switch ($token) { case '(': if ( isset($current) ) { $current->next = buildGraph($tokens); $current = $current->next; } else { $root->value[] = buildGraph($tokens); $current = end($root->value); } break; case ')': $current->next = &$root->next; return $root; case '|': $current->next = &$root->next; unset($current); break; default: if ( isset($current) ) { $current->next = new Element; $current = $current->next; } else { $root->value[] = new Element; $current = end($root->value); } $current->type = Element::TYPE_LITERAL; $current->value = $token; } } $root->next = Element::END_OF_STRING; return $root; } function getPaths($elt, $prefix = '') { if ( $elt === Element::END_OF_STRING ) { yield $prefix; return; } switch($elt->type) { case Element::TYPE_LITERAL: $prefix .= $elt->value; yield from getPaths($elt->next, $prefix); break; case Element::TYPE_GROUP: foreach ($elt->value as $value) { yield from getPaths($value, $prefix); } break; } } $pattern = 'chap(i|a) chap(o|a) p(a|i)t(a|i)p(o|a)'; // validation $validationPattern = '~ \A ( [^()]+ | \( (?1)* \) )* \z ~x'; if ( !preg_match($validationPattern, $pattern) ) throw new Exception('invalid pattern.'); // tokenization $tokens = (function ($regex) { if ( preg_match_all('~ [^()|]+ | (?<![^(|]) (?![^|)]) | [()|] ~x', $regex, $matches) ) yield from $matches[0]; })($pattern); $graph = buildGraph($tokens); foreach (getPaths($graph) as $path) { echo $path, PHP_EOL; }
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 8, Position 2 = 12
Branch analysis from position: 8
1 jumps found. (Code = 108) Position 1 = -2
Branch analysis from position: 12
2 jumps found. (Code = 77) Position 1 = 25, Position 2 = 29
Branch analysis from position: 25
2 jumps found. (Code = 78) Position 1 = 26, Position 2 = 29
Branch analysis from position: 26
1 jumps found. (Code = 42) Position 1 = 25
Branch analysis from position: 25
Branch analysis from position: 29
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 29
filename:       /in/BY44p
function name:  (null)
number of ops:  31
compiled vars:  !0 = $pattern, !1 = $validationPattern, !2 = $tokens, !3 = $graph, !4 = $path
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   77     0  E >   ASSIGN                                                   !0, 'chap%28i%7Ca%29+chap%28o%7Ca%29+p%28a%7Ci%29t%28a%7Ci%29p%28o%7Ca%29'
   80     1        ASSIGN                                                   !1, '%7E+%5CA+%28+%5B%5E%28%29%5D%2B+%7C+%5C%28+%28%3F1%29%2A+%5C%29+%29%2A+%5Cz+%7Ex'
   82     2        INIT_FCALL                                               'preg_match'
          3        SEND_VAR                                                 !1
          4        SEND_VAR                                                 !0
          5        DO_ICALL                                         $7      
          6        BOOL_NOT                                         ~8      $7
          7      > JMPZ                                                     ~8, ->12
   83     8    >   NEW                                              $9      'Exception'
          9        SEND_VAL_EX                                              'invalid+pattern.'
         10        DO_FCALL                                      0          
         11      > THROW                                         0          $9
   86    12    >   DECLARE_LAMBDA_FUNCTION                          ~11     [0]
   89    13        INIT_DYNAMIC_CALL                                        ~11
         14        SEND_VAR_EX                                              !0
         15        DO_FCALL                                      0  $12     
   86    16        ASSIGN                                                   !2, $12
   91    17        INIT_FCALL                                               'buildgraph'
         18        SEND_VAR                                                 !2
         19        DO_FCALL                                      0  $14     
         20        ASSIGN                                                   !3, $14
   93    21        INIT_FCALL                                               'getpaths'
         22        SEND_VAR                                                 !3
         23        DO_FCALL                                      0  $16     
         24      > FE_RESET_R                                       $17     $16, ->29
         25    > > FE_FETCH_R                                               $17, !4, ->29
   94    26    >   ECHO                                                     !4
         27        ECHO                                                     '%0A'
   93    28      > JMP                                                      ->25
         29    >   FE_FREE                                                  $17
   95    30      > RETURN                                                   1


Dynamic Functions:
Dynamic Function 0
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 8, Position 2 = 11
Branch analysis from position: 8
1 jumps found. (Code = 161) Position 1 = -2
Branch analysis from position: 11
filename:       /in/BY44p
function name:  {closure}
number of ops:  12
compiled vars:  !0 = $regex, !1 = $matches
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   86     0  E >   RECV                                             !0      
          1        GENERATOR_CREATE                                         
   87     2        INIT_FCALL                                               'preg_match_all'
          3        SEND_VAL                                                 '%7E+%5B%5E%28%29%7C%5D%2B+%7C+%28%3F%3C%21%5B%5E%28%7C%5D%29+%28%3F%21%5B%5E%7C%29%5D%29+%7C+%5B%28%29%7C%5D+%7Ex'
          4        SEND_VAR                                                 !0
          5        SEND_REF                                                 !1
          6        DO_ICALL                                         $2      
          7      > JMPZ                                                     $2, ->11
   88     8    >   FETCH_DIM_R                                      ~3      !1, 0
          9        YIELD_FROM                                       ~4      ~3
         10        FREE                                                     ~4
   89    11    > > GENERATOR_RETURN                                         

End of Dynamic Function 0

Function buildgraph:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 76
Branch analysis from position: 76
2 jumps found. (Code = 44) Position 1 = 79, Position 2 = 7
Branch analysis from position: 79
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 7
5 jumps found. (Code = 188) Position 1 = 20, Position 2 = 42, Position 3 = 47, Position 4 = 53, Position 5 = 13
Branch analysis from position: 20
2 jumps found. (Code = 43) Position 1 = 22, Position 2 = 30
Branch analysis from position: 22
1 jumps found. (Code = 42) Position 1 = 41
Branch analysis from position: 41
1 jumps found. (Code = 42) Position 1 = 76
Branch analysis from position: 76
Branch analysis from position: 30
1 jumps found. (Code = 42) Position 1 = 76
Branch analysis from position: 76
Branch analysis from position: 42
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 47
1 jumps found. (Code = 42) Position 1 = 76
Branch analysis from position: 76
Branch analysis from position: 53
2 jumps found. (Code = 43) Position 1 = 55, Position 2 = 62
Branch analysis from position: 55
1 jumps found. (Code = 42) Position 1 = 72
Branch analysis from position: 72
2 jumps found. (Code = 44) Position 1 = 79, Position 2 = 7
Branch analysis from position: 79
Branch analysis from position: 7
Branch analysis from position: 62
2 jumps found. (Code = 44) Position 1 = 79, Position 2 = 7
Branch analysis from position: 79
Branch analysis from position: 7
Branch analysis from position: 13
2 jumps found. (Code = 44) Position 1 = 15, Position 2 = 20
Branch analysis from position: 15
2 jumps found. (Code = 44) Position 1 = 17, Position 2 = 42
Branch analysis from position: 17
2 jumps found. (Code = 44) Position 1 = 19, Position 2 = 47
Branch analysis from position: 19
1 jumps found. (Code = 42) Position 1 = 53
Branch analysis from position: 53
Branch analysis from position: 47
Branch analysis from position: 42
Branch analysis from position: 20
filename:       /in/BY44p
function name:  buildGraph
number of ops:  83
compiled vars:  !0 = $tokens, !1 = $root, !2 = $token, !3 = $current
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   14     0  E >   RECV                                             !0      
   15     1        NEW                                              $4      'Element'
          2        DO_FCALL                                      0          
          3        ASSIGN                                                   !1, $4
   16     4        ASSIGN_OBJ                                               !1, 'type'
          5        OP_DATA                                                  1
   18     6      > JMP                                                      ->76
   19     7    >   INIT_METHOD_CALL                                         !0, 'current'
          8        DO_FCALL                                      0  $8      
          9        ASSIGN                                                   !2, $8
   20    10        INIT_METHOD_CALL                                         !0, 'next'
         11        DO_FCALL                                      0          
   21    12      > SWITCH_STRING                                            !2, [ '%28':->20, '%29':->42, '%7C':->47, ], ->53
   22    13    >   IS_EQUAL                                                 !2, '%28'
         14      > JMPNZ                                                    ~11, ->20
   32    15    >   IS_EQUAL                                                 !2, '%29'
         16      > JMPNZ                                                    ~11, ->42
   36    17    >   IS_EQUAL                                                 !2, '%7C'
         18      > JMPNZ                                                    ~11, ->47
         19    > > JMP                                                      ->53
   23    20    >   ISSET_ISEMPTY_CV                                         !3
         21      > JMPZ                                                     ~12, ->30
   24    22    >   INIT_FCALL_BY_NAME                                       'buildGraph'
         23        SEND_VAR_EX                                              !0
         24        DO_FCALL                                      0  $14     
         25        ASSIGN_OBJ                                               !3, 'next'
         26        OP_DATA                                                  $14
   25    27        FETCH_OBJ_R                                      ~15     !3, 'next'
         28        ASSIGN                                                   !3, ~15
   23    29      > JMP                                                      ->41
   27    30    >   INIT_FCALL_BY_NAME                                       'buildGraph'
         31        SEND_VAR_EX                                              !0
         32        DO_FCALL                                      0  $19     
         33        FETCH_OBJ_W                                      $17     !1, 'value'
         34        ASSIGN_DIM                                               $17
         35        OP_DATA                                                  $19
   28    36        INIT_FCALL                                               'end'
         37        FETCH_OBJ_W                                      $20     !1, 'value'
         38        SEND_REF                                                 $20
         39        DO_ICALL                                         $21     
         40        ASSIGN                                                   !3, $21
   30    41    > > JMP                                                      ->76
   33    42    >   FETCH_OBJ_W                                      $24     !1, 'next'
         43        MAKE_REF                                         $25     $24
         44        ASSIGN_OBJ_REF                                           !3, 'next'
         45        OP_DATA                                                  $25
   34    46      > RETURN                                                   !1
   37    47    >   FETCH_OBJ_W                                      $27     !1, 'next'
         48        MAKE_REF                                         $28     $27
         49        ASSIGN_OBJ_REF                                           !3, 'next'
         50        OP_DATA                                                  $28
   38    51        UNSET_CV                                                 !3
   39    52      > JMP                                                      ->76
   42    53    >   ISSET_ISEMPTY_CV                                         !3
         54      > JMPZ                                                     ~29, ->62
   43    55    >   NEW                                              $31     'Element'
         56        DO_FCALL                                      0          
         57        ASSIGN_OBJ                                               !3, 'next'
         58        OP_DATA                                                  $31
   44    59        FETCH_OBJ_R                                      ~33     !3, 'next'
         60        ASSIGN                                                   !3, ~33
   42    61      > JMP                                                      ->72
   46    62    >   NEW                                              $37     'Element'
         63        DO_FCALL                                      0          
         64        FETCH_OBJ_W                                      $35     !1, 'value'
         65        ASSIGN_DIM                                               $35
         66        OP_DATA                                                  $37
   47    67        INIT_FCALL                                               'end'
         68        FETCH_OBJ_W                                      $39     !1, 'value'
         69        SEND_REF                                                 $39
         70        DO_ICALL                                         $40     
         71        ASSIGN                                                   !3, $40
   49    72    >   ASSIGN_OBJ                                               !3, 'type'
         73        OP_DATA                                                  0
   50    74        ASSIGN_OBJ                                               !3, 'value'
         75        OP_DATA                                                  !2
   18    76    >   INIT_METHOD_CALL                                         !0, 'valid'
         77        DO_FCALL                                      0  $44     
         78      > JMPNZ                                                    $44, ->7
   53    79    >   ASSIGN_OBJ                                               !1, 'next'
         80        OP_DATA                                                  2
   54    81      > RETURN                                                   !1
   55    82*     > RETURN                                                   null

End of function buildgraph

Function getpaths:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 5, Position 2 = 7
Branch analysis from position: 5
1 jumps found. (Code = 161) Position 1 = -2
Branch analysis from position: 7
2 jumps found. (Code = 44) Position 1 = 10, Position 2 = 13
Branch analysis from position: 10
2 jumps found. (Code = 44) Position 1 = 12, Position 2 = 24
Branch analysis from position: 12
1 jumps found. (Code = 42) Position 1 = 36
Branch analysis from position: 36
1 jumps found. (Code = 161) Position 1 = -2
Branch analysis from position: 24
2 jumps found. (Code = 77) Position 1 = 26, Position 2 = 34
Branch analysis from position: 26
2 jumps found. (Code = 78) Position 1 = 27, Position 2 = 34
Branch analysis from position: 27
1 jumps found. (Code = 42) Position 1 = 26
Branch analysis from position: 26
Branch analysis from position: 34
1 jumps found. (Code = 42) Position 1 = 36
Branch analysis from position: 36
Branch analysis from position: 34
Branch analysis from position: 13
1 jumps found. (Code = 42) Position 1 = 36
Branch analysis from position: 36
filename:       /in/BY44p
function name:  getPaths
number of ops:  38
compiled vars:  !0 = $elt, !1 = $prefix, !2 = $value
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   57     0  E >   RECV                                             !0      
          1        RECV_INIT                                        !1      ''
          2        GENERATOR_CREATE                                         
   58     3        IS_IDENTICAL                                             !0, 2
          4      > JMPZ                                                     ~3, ->7
   59     5    >   YIELD                                                    !1
   60     6      > GENERATOR_RETURN                                         
   63     7    >   FETCH_OBJ_R                                      ~5      !0, 'type'
          8        CASE                                                     ~5, 0
          9      > JMPNZ                                                    ~6, ->13
         10    >   CASE                                                     ~5, 1
         11      > JMPNZ                                                    ~6, ->24
         12    > > JMP                                                      ->36
   65    13    >   FETCH_OBJ_R                                      ~7      !0, 'value'
         14        ASSIGN_OP                                     8          !1, ~7
   66    15        INIT_FCALL_BY_NAME                                       'getPaths'
         16        CHECK_FUNC_ARG                                           
         17        FETCH_OBJ_FUNC_ARG                               $9      !0, 'next'
         18        SEND_FUNC_ARG                                            $9
         19        SEND_VAR_EX                                              !1
         20        DO_FCALL                                      0  $10     
         21        YIELD_FROM                                       ~11     $10
         22        FREE                                                     ~11
   67    23      > JMP                                                      ->36
   70    24    >   FETCH_OBJ_R                                      ~12     !0, 'value'
         25      > FE_RESET_R                                       $13     ~12, ->34
         26    > > FE_FETCH_R                                               $13, !2, ->34
   71    27    >   INIT_FCALL_BY_NAME                                       'getPaths'
         28        SEND_VAR_EX                                              !2
         29        SEND_VAR_EX                                              !1
         30        DO_FCALL                                      0  $14     
         31        YIELD_FROM                                       ~15     $14
         32        FREE                                                     ~15
   70    33      > JMP                                                      ->26
         34    >   FE_FREE                                                  $13
   73    35      > JMP                                                      ->36
         36    >   FREE                                                     ~5
   75    37      > GENERATOR_RETURN                                         

End of function getpaths

Class Element: [no user functions]

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
149.74 ms | 1032 KiB | 18 Q