[Summary view] [Print] [Text view]

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