[Summary view] [Print] [Text view]

   1  <?php declare(strict_types=1);
   2  
   3  /**
   4  * @package   s9e\RegexpBuilder
   5  * @copyright Copyright (c) 2016-2022 The s9e authors
   6  * @license   http://www.opensource.org/licenses/mit-license.php The MIT License
   7  */
   8  namespace s9e\RegexpBuilder\Passes;
   9  
  10  use const false;
  11  use function array_diff_key, array_pop, array_unshift, count, end, is_array, serialize, unserialize;
  12  
  13  /**
  14  * Replaces (?:ab?|b)? with a?b?
  15  */
  16  class CoalesceOptionalStrings extends AbstractPass
  17  {
  18      /**
  19      * {@inheritdoc}
  20      */
  21  	protected function canRun(array $strings): bool
  22      {
  23          return ($this->isOptional && count($strings) > 1);
  24      }
  25  
  26      /**
  27      * {@inheritdoc}
  28      */
  29  	protected function runPass(array $strings): array
  30      {
  31          foreach ($this->getPrefixGroups($strings) as $suffix => $prefixStrings)
  32          {
  33              $suffix        = unserialize($suffix);
  34              $suffixStrings = array_diff_key($strings, $prefixStrings);
  35              if ($suffix === $this->buildSuffix($suffixStrings))
  36              {
  37                  $this->isOptional = false;
  38  
  39                  return $this->buildCoalescedStrings($prefixStrings, $suffix);
  40              }
  41          }
  42  
  43          return $strings;
  44      }
  45  
  46      /**
  47      * Build the final list of coalesced strings
  48      *
  49      * @param  array[] $prefixStrings
  50      * @param  array   $suffix
  51      * @return array[]
  52      */
  53  	protected function buildCoalescedStrings(array $prefixStrings, array $suffix): array
  54      {
  55          $strings = $this->runPass($this->buildPrefix($prefixStrings));
  56          if ($this->isSingleOptionalAlternation($strings))
  57          {
  58              // If the prefix has been remerged into a list of strings which contains only one string
  59              // of which the first element is an optional alternation, we only need to append the
  60              // suffix
  61              $strings[0][] = $suffix;
  62          }
  63          else
  64          {
  65              // Put the current list of strings that form the prefix into a new list of strings, of
  66              // which the only string is composed of our optional prefix followed by the suffix
  67              array_unshift($strings, []);
  68              $strings = [[$strings, $suffix]];
  69          }
  70  
  71          return $strings;
  72      }
  73  
  74      /**
  75      * Build the list of strings used as prefix
  76      *
  77      * @param  array[] $strings
  78      * @return array[]
  79      */
  80  	protected function buildPrefix(array $strings): array
  81      {
  82          $prefix = [];
  83          foreach ($strings as $string)
  84          {
  85              // Remove the last element (suffix) of each string before adding it
  86              array_pop($string);
  87              $prefix[] = $string;
  88          }
  89  
  90          return $prefix;
  91      }
  92  
  93      /**
  94      * Build a list of strings that matches any given strings or nothing
  95      *
  96      * Will unpack groups of single characters
  97      *
  98      * @param  array[] $strings
  99      * @return array[]
 100      */
 101  	protected function buildSuffix(array $strings): array
 102      {
 103          $suffix = [[]];
 104          foreach ($strings as $string)
 105          {
 106              if ($this->isCharacterClassString($string))
 107              {
 108                  foreach ($string[0] as $element)
 109                  {
 110                      $suffix[] = $element;
 111                  }
 112              }
 113              else
 114              {
 115                  $suffix[] = $string;
 116              }
 117          }
 118  
 119          return $suffix;
 120      }
 121  
 122      /**
 123      * Get the list of potential prefix strings grouped by identical suffix
 124      *
 125      * @param  array[] $strings
 126      * @return array
 127      */
 128  	protected function getPrefixGroups(array $strings): array
 129      {
 130          $groups = [];
 131          foreach ($strings as $k => $string)
 132          {
 133              if ($this->hasOptionalSuffix($string))
 134              {
 135                  $groups[serialize(end($string))][$k] = $string;
 136              }
 137          }
 138  
 139          return $groups;
 140      }
 141  
 142      /**
 143      * Test whether given list of strings starts with a single optional alternation
 144      *
 145      * @param  array $strings
 146      * @return bool
 147      */
 148  	protected function isSingleOptionalAlternation(array $strings): bool
 149      {
 150          return (count($strings) === 1 && is_array($strings[0][0]) && $strings[0][0][0] === []);
 151      }
 152  }