[ Index ]

PHP Cross Reference of DokuWiki

title

Body

[close]

/inc/Search/ -> Indexer.php (source)

   1  <?php
   2  
   3  namespace dokuwiki\Search;
   4  
   5  use dokuwiki\Utf8\Asian;
   6  use dokuwiki\Utf8\Clean;
   7  use dokuwiki\Utf8\PhpString;
   8  use dokuwiki\Extension\Event;
   9  
  10  /**
  11   * Class that encapsulates operations on the indexer database.
  12   *
  13   * @author Tom N Harris <tnharris@whoopdedo.org>
  14   */
  15  class Indexer
  16  {
  17      /**
  18       * @var array $pidCache Cache for getPID()
  19       */
  20      protected $pidCache = [];
  21  
  22      /**
  23       * Adds the contents of a page to the fulltext index
  24       *
  25       * The added text replaces previous words for the same page.
  26       * An empty value erases the page.
  27       *
  28       * @param string    $page   a page name
  29       * @param string    $text   the body of the page
  30       * @return string|boolean  the function completed successfully
  31       *
  32       * @author Tom N Harris <tnharris@whoopdedo.org>
  33       * @author Andreas Gohr <andi@splitbrain.org>
  34       */
  35      public function addPageWords($page, $text)
  36      {
  37          if (!$this->lock())
  38              return "locked";
  39  
  40          // load known documents
  41          $pid = $this->getPIDNoLock($page);
  42          if ($pid === false) {
  43              $this->unlock();
  44              return false;
  45          }
  46  
  47          $pagewords = [];
  48          // get word usage in page
  49          $words = $this->getPageWords($text);
  50          if ($words === false) {
  51              $this->unlock();
  52              return false;
  53          }
  54  
  55          if (!empty($words)) {
  56              foreach (array_keys($words) as $wlen) {
  57                  $index = $this->getIndex('i', $wlen);
  58                  foreach ($words[$wlen] as $wid => $freq) {
  59                      $idx = ($wid < count($index)) ? $index[$wid] : '';
  60                      $index[$wid] = $this->updateTuple($idx, $pid, $freq);
  61                      $pagewords[] = "$wlen*$wid";
  62                  }
  63                  if (!$this->saveIndex('i', $wlen, $index)) {
  64                      $this->unlock();
  65                      return false;
  66                  }
  67              }
  68          }
  69  
  70          // Remove obsolete index entries
  71          $pageword_idx = $this->getIndexKey('pageword', '', $pid);
  72          if ($pageword_idx !== '') {
  73              $oldwords = explode(':', $pageword_idx);
  74              $delwords = array_diff($oldwords, $pagewords);
  75              $upwords = [];
  76              foreach ($delwords as $word) {
  77                  if ($word != '') {
  78                      [$wlen, $wid] = explode('*', $word);
  79                      $wid = (int)$wid;
  80                      $upwords[$wlen][] = $wid;
  81                  }
  82              }
  83              foreach ($upwords as $wlen => $widx) {
  84                  $index = $this->getIndex('i', $wlen);
  85                  foreach ($widx as $wid) {
  86                      $index[$wid] = $this->updateTuple($index[$wid], $pid, 0);
  87                  }
  88                  $this->saveIndex('i', $wlen, $index);
  89              }
  90          }
  91          // Save the reverse index
  92          $pageword_idx = implode(':', $pagewords);
  93          if (!$this->saveIndexKey('pageword', '', $pid, $pageword_idx)) {
  94              $this->unlock();
  95              return false;
  96          }
  97  
  98          $this->unlock();
  99          return true;
 100      }
 101  
 102      /**
 103       * Split the words in a page and add them to the index.
 104       *
 105       * @param string    $text   content of the page
 106       * @return array            list of word IDs and number of times used
 107       *
 108       * @author Andreas Gohr <andi@splitbrain.org>
 109       * @author Christopher Smith <chris@jalakai.co.uk>
 110       * @author Tom N Harris <tnharris@whoopdedo.org>
 111       */
 112      protected function getPageWords($text)
 113      {
 114  
 115          $tokens = $this->tokenizer($text);
 116          $tokens = array_count_values($tokens);  // count the frequency of each token
 117  
 118          $words = [];
 119          foreach ($tokens as $w => $c) {
 120              $l = wordlen($w);
 121              if (isset($words[$l])) {
 122                  $words[$l][$w] = $c + ($words[$l][$w] ?? 0);
 123              } else {
 124                  $words[$l] = [$w => $c];
 125              }
 126          }
 127  
 128          // arrive here with $words = array(wordlen => array(word => frequency))
 129          $index = [];   //resulting index
 130          foreach (array_keys($words) as $wlen) {
 131              $word_idx = $this->getIndex('w', $wlen);
 132              $word_idx_modified = false;
 133              foreach ($words[$wlen] as $word => $freq) {
 134                  $word = (string)$word;
 135                  $wid = array_search($word, $word_idx, true);
 136                  if ($wid === false) {
 137                      $wid = count($word_idx);
 138                      $word_idx[] = $word;
 139                      $word_idx_modified = true;
 140                  }
 141                  if (!isset($index[$wlen]))
 142                      $index[$wlen] = [];
 143                  $index[$wlen][$wid] = $freq;
 144              }
 145              // save back the word index
 146              if ($word_idx_modified && !$this->saveIndex('w', $wlen, $word_idx))
 147                  return false;
 148          }
 149  
 150          return $index;
 151      }
 152  
 153      /**
 154       * Add/update keys to/of the metadata index.
 155       *
 156       * Adding new keys does not remove other keys for the page.
 157       * An empty value will erase the key.
 158       * The $key parameter can be an array to add multiple keys. $value will
 159       * not be used if $key is an array.
 160       *
 161       * @param string    $page   a page name
 162       * @param mixed     $key    a key string or array of key=>value pairs
 163       * @param mixed     $value  the value or list of values
 164       * @return boolean|string     the function completed successfully
 165       *
 166       * @author Tom N Harris <tnharris@whoopdedo.org>
 167       * @author Michael Hamann <michael@content-space.de>
 168       */
 169      public function addMetaKeys($page, $key, $value = null)
 170      {
 171          if (!is_array($key)) {
 172              $key = [$key => $value];
 173          } elseif (!is_null($value)) {
 174              // $key is array, but $value is not null
 175              trigger_error("array passed to addMetaKeys but value is not null", E_USER_WARNING);
 176          }
 177  
 178          if (!$this->lock())
 179              return "locked";
 180  
 181          // load known documents
 182          $pid = $this->getPIDNoLock($page);
 183          if ($pid === false) {
 184              $this->unlock();
 185              return false;
 186          }
 187  
 188          // Special handling for titles so the index file is simpler
 189          if (isset($key['title'])) {
 190              $value = $key['title'];
 191              if (is_array($value)) {
 192                  $value = $value[0];
 193              }
 194              $this->saveIndexKey('title', '', $pid, $value);
 195              unset($key['title']);
 196          }
 197  
 198          foreach ($key as $name => $values) {
 199              $metaname = idx_cleanName($name);
 200              $this->addIndexKey('metadata', '', $metaname);
 201              $metaidx = $this->getIndex($metaname . '_i', '');
 202              $metawords = $this->getIndex($metaname . '_w', '');
 203              $addwords = false;
 204  
 205              if (!is_array($values)) $values = [$values];
 206  
 207              $val_idx = $this->getIndexKey($metaname . '_p', '', $pid);
 208              if ($val_idx !== '') {
 209                  $val_idx = explode(':', $val_idx);
 210                  // -1 means remove, 0 keep, 1 add
 211                  $val_idx = array_combine($val_idx, array_fill(0, count($val_idx), -1));
 212              } else {
 213                  $val_idx = [];
 214              }
 215  
 216              foreach ($values as $val) {
 217                  $val = (string)$val;
 218                  if ($val !== "") {
 219                      $id = array_search($val, $metawords, true);
 220                      if ($id === false) {
 221                          // didn't find $val, so we'll add it to the end of metawords and create a placeholder in metaidx
 222                          $id = count($metawords);
 223                          $metawords[$id] = $val;
 224                          $metaidx[$id] = '';
 225                          $addwords = true;
 226                      }
 227                      // test if value is already in the index
 228                      if (isset($val_idx[$id]) && $val_idx[$id] <= 0) {
 229                          $val_idx[$id] = 0;
 230                      } else { // else add it
 231                          $val_idx[$id] = 1;
 232                      }
 233                  }
 234              }
 235  
 236              if ($addwords) {
 237                  $this->saveIndex($metaname . '_w', '', $metawords);
 238              }
 239              $vals_changed = false;
 240              foreach ($val_idx as $id => $action) {
 241                  if ($action == -1) {
 242                      $metaidx[$id] = $this->updateTuple($metaidx[$id], $pid, 0);
 243                      $vals_changed = true;
 244                      unset($val_idx[$id]);
 245                  } elseif ($action == 1) {
 246                      $metaidx[$id] = $this->updateTuple($metaidx[$id], $pid, 1);
 247                      $vals_changed = true;
 248                  }
 249              }
 250  
 251              if ($vals_changed) {
 252                  $this->saveIndex($metaname . '_i', '', $metaidx);
 253                  $val_idx = implode(':', array_keys($val_idx));
 254                  $this->saveIndexKey($metaname . '_p', '', $pid, $val_idx);
 255              }
 256  
 257              unset($metaidx);
 258              unset($metawords);
 259          }
 260  
 261          $this->unlock();
 262          return true;
 263      }
 264  
 265      /**
 266       * Rename a page in the search index without changing the indexed content. This function doesn't check if the
 267       * old or new name exists in the filesystem. It returns an error if the old page isn't in the page list of the
 268       * indexer and it deletes all previously indexed content of the new page.
 269       *
 270       * @param string $oldpage The old page name
 271       * @param string $newpage The new page name
 272       * @return string|bool If the page was successfully renamed, can be a message in the case of an error
 273       */
 274      public function renamePage($oldpage, $newpage)
 275      {
 276          if (!$this->lock()) return 'locked';
 277  
 278          $pages = $this->getPages();
 279  
 280          $id = array_search($oldpage, $pages, true);
 281          if ($id === false) {
 282              $this->unlock();
 283              return 'page is not in index';
 284          }
 285  
 286          $new_id = array_search($newpage, $pages, true);
 287          if ($new_id !== false) {
 288              // make sure the page is not in the index anymore
 289              if (!$this->deletePageNoLock($newpage)) {
 290                  return false;
 291              }
 292  
 293              $pages[$new_id] = 'deleted:' . time() . random_int(0, 9999);
 294          }
 295  
 296          $pages[$id] = $newpage;
 297  
 298          // update index
 299          if (!$this->saveIndex('page', '', $pages)) {
 300              $this->unlock();
 301              return false;
 302          }
 303  
 304          // reset the pid cache
 305          $this->pidCache = [];
 306  
 307          $this->unlock();
 308          return true;
 309      }
 310  
 311      /**
 312       * Renames a meta value in the index. This doesn't change the meta value in the pages, it assumes that all pages
 313       * will be updated.
 314       *
 315       * @param string $key       The metadata key of which a value shall be changed
 316       * @param string $oldvalue  The old value that shall be renamed
 317       * @param string $newvalue  The new value to which the old value shall be renamed, if exists values will be merged
 318       * @return bool|string      If renaming the value has been successful, false or error message on error.
 319       */
 320      public function renameMetaValue($key, $oldvalue, $newvalue)
 321      {
 322          if (!$this->lock()) return 'locked';
 323  
 324          // change the relation references index
 325          $metavalues = $this->getIndex($key, '_w');
 326          $oldid = array_search($oldvalue, $metavalues, true);
 327          if ($oldid !== false) {
 328              $newid = array_search($newvalue, $metavalues, true);
 329              if ($newid !== false) {
 330                  // free memory
 331                  unset($metavalues);
 332  
 333                  // okay, now we have two entries for the same value. we need to merge them.
 334                  $indexline = $this->getIndexKey($key . '_i', '', $oldid);
 335                  if ($indexline != '') {
 336                      $newindexline = $this->getIndexKey($key . '_i', '', $newid);
 337                      $pagekeys     = $this->getIndex($key . '_p', '');
 338                      $parts = explode(':', $indexline);
 339                      foreach ($parts as $part) {
 340                          [$id, $count] = explode('*', $part);
 341                          $newindexline =  $this->updateTuple($newindexline, $id, $count);
 342  
 343                          $keyline = explode(':', $pagekeys[$id]);
 344                          // remove old meta value
 345                          $keyline = array_diff($keyline, [$oldid]);
 346                          // add new meta value when not already present
 347                          if (!in_array($newid, $keyline)) {
 348                              $keyline[] = $newid;
 349                          }
 350                          $pagekeys[$id] = implode(':', $keyline);
 351                      }
 352                      $this->saveIndex($key . '_p', '', $pagekeys);
 353                      unset($pagekeys);
 354                      $this->saveIndexKey($key . '_i', '', $oldid, '');
 355                      $this->saveIndexKey($key . '_i', '', $newid, $newindexline);
 356                  }
 357              } else {
 358                  $metavalues[$oldid] = $newvalue;
 359                  if (!$this->saveIndex($key . '_w', '', $metavalues)) {
 360                      $this->unlock();
 361                      return false;
 362                  }
 363              }
 364          }
 365  
 366          $this->unlock();
 367          return true;
 368      }
 369  
 370      /**
 371       * Remove a page from the index
 372       *
 373       * Erases entries in all known indexes.
 374       *
 375       * @param string    $page   a page name
 376       * @return string|boolean  the function completed successfully
 377       *
 378       * @author Tom N Harris <tnharris@whoopdedo.org>
 379       */
 380      public function deletePage($page)
 381      {
 382          if (!$this->lock())
 383              return "locked";
 384  
 385          $result = $this->deletePageNoLock($page);
 386  
 387          $this->unlock();
 388  
 389          return $result;
 390      }
 391  
 392      /**
 393       * Remove a page from the index without locking the index, only use this function if the index is already locked
 394       *
 395       * Erases entries in all known indexes.
 396       *
 397       * @param string    $page   a page name
 398       * @return boolean          the function completed successfully
 399       *
 400       * @author Tom N Harris <tnharris@whoopdedo.org>
 401       */
 402      protected function deletePageNoLock($page)
 403      {
 404          // load known documents
 405          $pid = $this->getPIDNoLock($page);
 406          if ($pid === false) {
 407              return false;
 408          }
 409  
 410          // Remove obsolete index entries
 411          $pageword_idx = $this->getIndexKey('pageword', '', $pid);
 412          if ($pageword_idx !== '') {
 413              $delwords = explode(':', $pageword_idx);
 414              $upwords = [];
 415              foreach ($delwords as $word) {
 416                  if ($word != '') {
 417                      [$wlen, $wid] = explode('*', $word);
 418                      $wid = (int)$wid;
 419                      $upwords[$wlen][] = $wid;
 420                  }
 421              }
 422              foreach ($upwords as $wlen => $widx) {
 423                  $index = $this->getIndex('i', $wlen);
 424                  foreach ($widx as $wid) {
 425                      $index[$wid] = $this->updateTuple($index[$wid], $pid, 0);
 426                  }
 427                  $this->saveIndex('i', $wlen, $index);
 428              }
 429          }
 430          // Save the reverse index
 431          if (!$this->saveIndexKey('pageword', '', $pid, "")) {
 432              return false;
 433          }
 434  
 435          $this->saveIndexKey('title', '', $pid, "");
 436          $keyidx = $this->getIndex('metadata', '');
 437          foreach ($keyidx as $metaname) {
 438              $val_idx = explode(':', $this->getIndexKey($metaname . '_p', '', $pid));
 439              $meta_idx = $this->getIndex($metaname . '_i', '');
 440              foreach ($val_idx as $id) {
 441                  if ($id === '') continue;
 442                  $meta_idx[$id] = $this->updateTuple($meta_idx[$id], $pid, 0);
 443              }
 444              $this->saveIndex($metaname . '_i', '', $meta_idx);
 445              $this->saveIndexKey($metaname . '_p', '', $pid, '');
 446          }
 447  
 448          return true;
 449      }
 450  
 451      /**
 452       * Clear the whole index
 453       *
 454       * @return bool If the index has been cleared successfully
 455       */
 456      public function clear()
 457      {
 458          global $conf;
 459  
 460          if (!$this->lock()) return false;
 461  
 462          @unlink($conf['indexdir'] . '/page.idx');
 463          @unlink($conf['indexdir'] . '/title.idx');
 464          @unlink($conf['indexdir'] . '/pageword.idx');
 465          @unlink($conf['indexdir'] . '/metadata.idx');
 466          $dir = @opendir($conf['indexdir']);
 467          if ($dir !== false) {
 468              while (($f = readdir($dir)) !== false) {
 469                  if (
 470                      str_ends_with($f, '.idx') &&
 471                      (str_starts_with($f, 'i') ||
 472                       str_starts_with($f, 'w') ||
 473                       str_ends_with($f, '_w.idx') ||
 474                       str_ends_with($f, '_i.idx') ||
 475                       str_ends_with($f, '_p.idx'))
 476                  )
 477                      @unlink($conf['indexdir'] . "/$f");
 478              }
 479          }
 480          @unlink($conf['indexdir'] . '/lengths.idx');
 481  
 482          // clear the pid cache
 483          $this->pidCache = [];
 484  
 485          $this->unlock();
 486          return true;
 487      }
 488  
 489      /**
 490       * Split the text into words for fulltext search
 491       *
 492       * TODO: does this also need &$stopwords ?
 493       *
 494       * @triggers INDEXER_TEXT_PREPARE
 495       * This event allows plugins to modify the text before it gets tokenized.
 496       * Plugins intercepting this event should also intercept INDEX_VERSION_GET
 497       *
 498       * @param string    $text   plain text
 499       * @param boolean   $wc     are wildcards allowed?
 500       * @return array            list of words in the text
 501       *
 502       * @author Tom N Harris <tnharris@whoopdedo.org>
 503       * @author Andreas Gohr <andi@splitbrain.org>
 504       */
 505      public function tokenizer($text, $wc = false)
 506      {
 507          $wc = ($wc) ? '' : '\*';
 508          $stopwords =& idx_get_stopwords();
 509  
 510          // prepare the text to be tokenized
 511          $evt = new Event('INDEXER_TEXT_PREPARE', $text);
 512          if ($evt->advise_before(true)) {
 513              if (preg_match('/[^0-9A-Za-z ]/u', $text)) {
 514                  $text = Asian::separateAsianWords($text);
 515              }
 516          }
 517          $evt->advise_after();
 518          unset($evt);
 519  
 520          $text = strtr(
 521              $text,
 522              ["\r" => ' ', "\n" => ' ', "\t" => ' ', "\xC2\xAD" => '']
 523          );
 524          if (preg_match('/[^0-9A-Za-z ]/u', $text))
 525              $text = Clean::stripspecials($text, ' ', '\._\-:' . $wc);
 526  
 527          $wordlist = explode(' ', $text);
 528          foreach ($wordlist as $i => $word) {
 529              $wordlist[$i] = (preg_match('/[^0-9A-Za-z]/u', $word)) ?
 530                  PhpString::strtolower($word) : strtolower($word);
 531          }
 532  
 533          foreach ($wordlist as $i => $word) {
 534              if (
 535                  (!is_numeric($word) && strlen($word) < IDX_MINWORDLENGTH)
 536                  || in_array($word, $stopwords, true)
 537              )
 538                  unset($wordlist[$i]);
 539          }
 540          return array_values($wordlist);
 541      }
 542  
 543      /**
 544       * Get the numeric PID of a page
 545       *
 546       * @param string $page The page to get the PID for
 547       * @return bool|int The page id on success, false on error
 548       */
 549      public function getPID($page)
 550      {
 551          // return PID without locking when it is in the cache
 552          if (isset($this->pidCache[$page])) return $this->pidCache[$page];
 553  
 554          if (!$this->lock())
 555              return false;
 556  
 557          // load known documents
 558          $pid = $this->getPIDNoLock($page);
 559          if ($pid === false) {
 560              $this->unlock();
 561              return false;
 562          }
 563  
 564          $this->unlock();
 565          return $pid;
 566      }
 567  
 568      /**
 569       * Get the numeric PID of a page without locking the index.
 570       * Only use this function when the index is already locked.
 571       *
 572       * @param string $page The page to get the PID for
 573       * @return bool|int The page id on success, false on error
 574       */
 575      protected function getPIDNoLock($page)
 576      {
 577          // avoid expensive addIndexKey operation for the most recently requested pages by using a cache
 578          if (isset($this->pidCache[$page])) return $this->pidCache[$page];
 579          $pid = $this->addIndexKey('page', '', $page);
 580          // limit cache to 10 entries by discarding the oldest element as in DokuWiki usually only the most recently
 581          // added item will be requested again
 582          if (count($this->pidCache) > 10) array_shift($this->pidCache);
 583          $this->pidCache[$page] = $pid;
 584          return $pid;
 585      }
 586  
 587      /**
 588       * Get the page id of a numeric PID
 589       *
 590       * @param int $pid The PID to get the page id for
 591       * @return string The page id
 592       */
 593      public function getPageFromPID($pid)
 594      {
 595          return $this->getIndexKey('page', '', $pid);
 596      }
 597  
 598      /**
 599       * Find pages in the fulltext index containing the words,
 600       *
 601       * The search words must be pre-tokenized, meaning only letters and
 602       * numbers with an optional wildcard
 603       *
 604       * The returned array will have the original tokens as key. The values
 605       * in the returned list is an array with the page names as keys and the
 606       * number of times that token appears on the page as value.
 607       *
 608       * @param array  $tokens list of words to search for
 609       * @return array         list of page names with usage counts
 610       *
 611       * @author Tom N Harris <tnharris@whoopdedo.org>
 612       * @author Andreas Gohr <andi@splitbrain.org>
 613       */
 614      public function lookup(&$tokens)
 615      {
 616          $result = [];
 617          $wids = $this->getIndexWords($tokens, $result);
 618          if (empty($wids)) return [];
 619          // load known words and documents
 620          $page_idx = $this->getIndex('page', '');
 621          $docs = [];
 622          foreach (array_keys($wids) as $wlen) {
 623              $wids[$wlen] = array_unique($wids[$wlen]);
 624              $index = $this->getIndex('i', $wlen);
 625              foreach ($wids[$wlen] as $ixid) {
 626                  if ($ixid < count($index))
 627                      $docs["$wlen*$ixid"] = $this->parseTuples($page_idx, $index[$ixid]);
 628              }
 629          }
 630          // merge found pages into final result array
 631          $final = [];
 632          foreach ($result as $word => $res) {
 633              $final[$word] = [];
 634              foreach ($res as $wid) {
 635                  // handle the case when ($ixid < count($index)) has been false
 636                  // and thus $docs[$wid] hasn't been set.
 637                  if (!isset($docs[$wid])) continue;
 638                  $hits = &$docs[$wid];
 639                  foreach ($hits as $hitkey => $hitcnt) {
 640                      // make sure the document still exists
 641                      if (!page_exists($hitkey, '', false)) continue;
 642                      if (!isset($final[$word][$hitkey]))
 643                          $final[$word][$hitkey] = $hitcnt;
 644                      else $final[$word][$hitkey] += $hitcnt;
 645                  }
 646              }
 647          }
 648          return $final;
 649      }
 650  
 651      /**
 652       * Find pages containing a metadata key.
 653       *
 654       * The metadata values are compared as case-sensitive strings. Pass a
 655       * callback function that returns true or false to use a different
 656       * comparison function. The function will be called with the $value being
 657       * searched for as the first argument, and the word in the index as the
 658       * second argument. The function preg_match can be used directly if the
 659       * values are regexes.
 660       *
 661       * @param string    $key    name of the metadata key to look for
 662       * @param string    $value  search term to look for, must be a string or array of strings
 663       * @param callback  $func   comparison function
 664       * @return array            lists with page names, keys are query values if $value is array
 665       *
 666       * @author Tom N Harris <tnharris@whoopdedo.org>
 667       * @author Michael Hamann <michael@content-space.de>
 668       */
 669      public function lookupKey($key, &$value, $func = null)
 670      {
 671          if (!is_array($value))
 672              $value_array = [$value];
 673          else $value_array =& $value;
 674  
 675          // the matching ids for the provided value(s)
 676          $value_ids = [];
 677  
 678          $metaname = idx_cleanName($key);
 679  
 680          // get all words in order to search the matching ids
 681          if ($key == 'title') {
 682              $words = $this->getIndex('title', '');
 683          } else {
 684              $words = $this->getIndex($metaname . '_w', '');
 685          }
 686  
 687          if (!is_null($func)) {
 688              foreach ($value_array as $val) {
 689                  foreach ($words as $i => $word) {
 690                      if (call_user_func_array($func, [$val, $word]))
 691                          $value_ids[$i][] = $val;
 692                  }
 693              }
 694          } else {
 695              foreach ($value_array as $val) {
 696                  $xval = $val;
 697                  $caret = '^';
 698                  $dollar = '$';
 699                  // check for wildcards
 700                  if (str_starts_with($xval, '*')) {
 701                      $xval = substr($xval, 1);
 702                      $caret = '';
 703                  }
 704                  if (str_ends_with($xval, '*')) {
 705                      $xval = substr($xval, 0, -1);
 706                      $dollar = '';
 707                  }
 708                  if (!$caret || !$dollar) {
 709                      $re = $caret . preg_quote($xval, '/') . $dollar;
 710                      foreach (array_keys(preg_grep('/' . $re . '/', $words)) as $i)
 711                          $value_ids[$i][] = $val;
 712                  } elseif (($i = array_search($val, $words, true)) !== false) {
 713                      $value_ids[$i][] = $val;
 714                  }
 715              }
 716          }
 717  
 718          unset($words); // free the used memory
 719  
 720          // initialize the result so it won't be null
 721          $result = [];
 722          foreach ($value_array as $val) {
 723              $result[$val] = [];
 724          }
 725  
 726          $page_idx = $this->getIndex('page', '');
 727  
 728          // Special handling for titles
 729          if ($key == 'title') {
 730              foreach ($value_ids as $pid => $val_list) {
 731                  $page = $page_idx[$pid];
 732                  foreach ($val_list as $val) {
 733                      $result[$val][] = $page;
 734                  }
 735              }
 736          } else {
 737              // load all lines and pages so the used lines can be taken and matched with the pages
 738              $lines = $this->getIndex($metaname . '_i', '');
 739  
 740              foreach ($value_ids as $value_id => $val_list) {
 741                  // parse the tuples of the form page_id*1:page2_id*1 and so on, return value
 742                  // is an array with page_id => 1, page2_id => 1 etc. so take the keys only
 743                  $pages = array_keys($this->parseTuples($page_idx, $lines[$value_id]));
 744                  foreach ($val_list as $val) {
 745                      $result[$val] = [...$result[$val], ...$pages];
 746                  }
 747              }
 748          }
 749          if (!is_array($value)) $result = $result[$value];
 750          return $result;
 751      }
 752  
 753      /**
 754       * Find the index ID of each search term.
 755       *
 756       * The query terms should only contain valid characters, with a '*' at
 757       * either the beginning or end of the word (or both).
 758       * The $result parameter can be used to merge the index locations with
 759       * the appropriate query term.
 760       *
 761       * @param array  $words  The query terms.
 762       * @param array  $result Set to word => array("length*id" ...)
 763       * @return array         Set to length => array(id ...)
 764       *
 765       * @author Tom N Harris <tnharris@whoopdedo.org>
 766       */
 767      protected function getIndexWords(&$words, &$result)
 768      {
 769          $tokens = [];
 770          $tokenlength = [];
 771          $tokenwild = [];
 772          foreach ($words as $word) {
 773              $result[$word] = [];
 774              $caret = '^';
 775              $dollar = '$';
 776              $xword = $word;
 777              $wlen = wordlen($word);
 778  
 779              // check for wildcards
 780              if (str_starts_with($xword, '*')) {
 781                  $xword = substr($xword, 1);
 782                  $caret = '';
 783                  --$wlen;
 784              }
 785              if (str_ends_with($xword, '*')) {
 786                  $xword = substr($xword, 0, -1);
 787                  $dollar = '';
 788                  --$wlen;
 789              }
 790              if ($wlen < IDX_MINWORDLENGTH && $caret && $dollar && !is_numeric($xword))
 791                  continue;
 792              if (!isset($tokens[$xword]))
 793                  $tokenlength[$wlen][] = $xword;
 794              if (!$caret || !$dollar) {
 795                  $re = $caret . preg_quote($xword, '/') . $dollar;
 796                  $tokens[$xword][] = [$word, '/' . $re . '/'];
 797                  if (!isset($tokenwild[$xword]))
 798                      $tokenwild[$xword] = $wlen;
 799              } else {
 800                  $tokens[$xword][] = [$word, null];
 801              }
 802          }
 803          asort($tokenwild);
 804          // $tokens = array( base word => array( [ query term , regexp ] ... ) ... )
 805          // $tokenlength = array( base word length => base word ... )
 806          // $tokenwild = array( base word => base word length ... )
 807          $length_filter = $tokenwild === [] ? $tokenlength : min(array_keys($tokenlength));
 808          $indexes_known = $this->indexLengths($length_filter);
 809          if ($tokenwild !== []) sort($indexes_known);
 810          // get word IDs
 811          $wids = [];
 812          foreach ($indexes_known as $ixlen) {
 813              $word_idx = $this->getIndex('w', $ixlen);
 814              // handle exact search
 815              if (isset($tokenlength[$ixlen])) {
 816                  foreach ($tokenlength[$ixlen] as $xword) {
 817                      $wid = array_search($xword, $word_idx, true);
 818                      if ($wid !== false) {
 819                          $wids[$ixlen][] = $wid;
 820                          foreach ($tokens[$xword] as $w)
 821                              $result[$w[0]][] = "$ixlen*$wid";
 822                      }
 823                  }
 824              }
 825              // handle wildcard search
 826              foreach ($tokenwild as $xword => $wlen) {
 827                  if ($wlen >= $ixlen) break;
 828                  foreach ($tokens[$xword] as $w) {
 829                      if (is_null($w[1])) continue;
 830                      foreach (array_keys(preg_grep($w[1], $word_idx)) as $wid) {
 831                          $wids[$ixlen][] = $wid;
 832                          $result[$w[0]][] = "$ixlen*$wid";
 833                      }
 834                  }
 835              }
 836          }
 837          return $wids;
 838      }
 839  
 840      /**
 841       * Return a list of all pages
 842       * Warning: pages may not exist!
 843       *
 844       * @param string    $key    list only pages containing the metadata key (optional)
 845       * @return array            list of page names
 846       *
 847       * @author Tom N Harris <tnharris@whoopdedo.org>
 848       */
 849      public function getPages($key = null)
 850      {
 851          $page_idx = $this->getIndex('page', '');
 852          if (is_null($key)) return $page_idx;
 853  
 854          $metaname = idx_cleanName($key);
 855  
 856          // Special handling for titles
 857          if ($key == 'title') {
 858              $title_idx = $this->getIndex('title', '');
 859              array_splice($page_idx, count($title_idx));
 860              foreach ($title_idx as $i => $title)
 861                  if ($title === "") unset($page_idx[$i]);
 862              return array_values($page_idx);
 863          }
 864  
 865          $pages = [];
 866          $lines = $this->getIndex($metaname . '_i', '');
 867          foreach ($lines as $line) {
 868              $pages = array_merge($pages, $this->parseTuples($page_idx, $line));
 869          }
 870          return array_keys($pages);
 871      }
 872  
 873      /**
 874       * Return a list of words sorted by number of times used
 875       *
 876       * @param int       $min    bottom frequency threshold
 877       * @param int       $max    upper frequency limit. No limit if $max<$min
 878       * @param int       $minlen minimum length of words to count
 879       * @param string    $key    metadata key to list. Uses the fulltext index if not given
 880       * @return array            list of words as the keys and frequency as values
 881       *
 882       * @author Tom N Harris <tnharris@whoopdedo.org>
 883       */
 884      public function histogram($min = 1, $max = 0, $minlen = 3, $key = null)
 885      {
 886          if ($min < 1)
 887              $min = 1;
 888          if ($max < $min)
 889              $max = 0;
 890  
 891          $result = [];
 892  
 893          if ($key == 'title') {
 894              $index = $this->getIndex('title', '');
 895              $index = array_count_values($index);
 896              foreach ($index as $val => $cnt) {
 897                  if ($cnt >= $min && (!$max || $cnt <= $max) && strlen($val) >= $minlen)
 898                      $result[$val] = $cnt;
 899              }
 900          } elseif (!is_null($key)) {
 901              $metaname = idx_cleanName($key);
 902              $index = $this->getIndex($metaname . '_i', '');
 903              $val_idx = [];
 904              foreach ($index as $wid => $line) {
 905                  $freq = $this->countTuples($line);
 906                  if ($freq >= $min && (!$max || $freq <= $max))
 907                      $val_idx[$wid] = $freq;
 908              }
 909              if (!empty($val_idx)) {
 910                  $words = $this->getIndex($metaname . '_w', '');
 911                  foreach ($val_idx as $wid => $freq) {
 912                      if (strlen($words[$wid]) >= $minlen)
 913                          $result[$words[$wid]] = $freq;
 914                  }
 915              }
 916          } else {
 917              $lengths = idx_listIndexLengths();
 918              foreach ($lengths as $length) {
 919                  if ($length < $minlen) continue;
 920                  $index = $this->getIndex('i', $length);
 921                  $words = null;
 922                  foreach ($index as $wid => $line) {
 923                      $freq = $this->countTuples($line);
 924                      if ($freq >= $min && (!$max || $freq <= $max)) {
 925                          if ($words === null)
 926                              $words = $this->getIndex('w', $length);
 927                          $result[$words[$wid]] = $freq;
 928                      }
 929                  }
 930              }
 931          }
 932  
 933          arsort($result);
 934          return $result;
 935      }
 936  
 937      /**
 938       * Lock the indexer.
 939       *
 940       * @author Tom N Harris <tnharris@whoopdedo.org>
 941       *
 942       * @return bool|string
 943       */
 944      protected function lock()
 945      {
 946          global $conf;
 947          $status = true;
 948          $run = 0;
 949          $lock = $conf['lockdir'] . '/_indexer.lock';
 950          while (!@mkdir($lock)) {
 951              usleep(50);
 952              if (is_dir($lock) && time() - @filemtime($lock) > 60 * 5) {
 953                  // looks like a stale lock - remove it
 954                  if (!@rmdir($lock)) {
 955                      $status = "removing the stale lock failed";
 956                      return false;
 957                  } else {
 958                      $status = "stale lock removed";
 959                  }
 960              } elseif ($run++ == 1000) {
 961                  // we waited 5 seconds for that lock
 962                  return false;
 963              }
 964          }
 965          if ($conf['dperm']) {
 966              chmod($lock, $conf['dperm']);
 967          }
 968          return $status;
 969      }
 970  
 971      /**
 972       * Release the indexer lock.
 973       *
 974       * @author Tom N Harris <tnharris@whoopdedo.org>
 975       *
 976       * @return bool
 977       */
 978      protected function unlock()
 979      {
 980          global $conf;
 981          @rmdir($conf['lockdir'] . '/_indexer.lock');
 982          return true;
 983      }
 984  
 985      /**
 986       * Retrieve the entire index.
 987       *
 988       * The $suffix argument is for an index that is split into
 989       * multiple parts. Different index files should use different
 990       * base names.
 991       *
 992       * @param string    $idx    name of the index
 993       * @param string    $suffix subpart identifier
 994       * @return array            list of lines without CR or LF
 995       *
 996       * @author Tom N Harris <tnharris@whoopdedo.org>
 997       */
 998      protected function getIndex($idx, $suffix)
 999      {
1000          global $conf;
1001          $fn = $conf['indexdir'] . '/' . $idx . $suffix . '.idx';
1002          if (!file_exists($fn)) return [];
1003          return file($fn, FILE_IGNORE_NEW_LINES);
1004      }
1005  
1006      /**
1007       * Replace the contents of the index with an array.
1008       *
1009       * @param string    $idx    name of the index
1010       * @param string    $suffix subpart identifier
1011       * @param array     $lines  list of lines without LF
1012       * @return bool             If saving succeeded
1013       *
1014       * @author Tom N Harris <tnharris@whoopdedo.org>
1015       */
1016      protected function saveIndex($idx, $suffix, &$lines)
1017      {
1018          global $conf;
1019          $fn = $conf['indexdir'] . '/' . $idx . $suffix;
1020          $fh = @fopen($fn . '.tmp', 'w');
1021          if (!$fh) return false;
1022          fwrite($fh, implode("\n", $lines));
1023          if (!empty($lines))
1024              fwrite($fh, "\n");
1025          fclose($fh);
1026          if ($conf['fperm'])
1027              chmod($fn . '.tmp', $conf['fperm']);
1028          io_rename($fn . '.tmp', $fn . '.idx');
1029          return true;
1030      }
1031  
1032      /**
1033       * Retrieve a line from the index.
1034       *
1035       * @param string    $idx    name of the index
1036       * @param string    $suffix subpart identifier
1037       * @param int       $id     the line number
1038       * @return string           a line with trailing whitespace removed
1039       *
1040       * @author Tom N Harris <tnharris@whoopdedo.org>
1041       */
1042      protected function getIndexKey($idx, $suffix, $id)
1043      {
1044          global $conf;
1045          $fn = $conf['indexdir'] . '/' . $idx . $suffix . '.idx';
1046          if (!file_exists($fn)) return '';
1047          $fh = @fopen($fn, 'r');
1048          if (!$fh) return '';
1049          $ln = -1;
1050          while (($line = fgets($fh)) !== false) {
1051              if (++$ln == $id) break;
1052          }
1053          fclose($fh);
1054          return rtrim((string)$line);
1055      }
1056  
1057      /**
1058       * Write a line into the index.
1059       *
1060       * @param string    $idx    name of the index
1061       * @param string    $suffix subpart identifier
1062       * @param int       $id     the line number
1063       * @param string    $line   line to write
1064       * @return bool             If saving succeeded
1065       *
1066       * @author Tom N Harris <tnharris@whoopdedo.org>
1067       */
1068      protected function saveIndexKey($idx, $suffix, $id, $line)
1069      {
1070          global $conf;
1071          if (!str_ends_with($line, "\n"))
1072              $line .= "\n";
1073          $fn = $conf['indexdir'] . '/' . $idx . $suffix;
1074          $fh = @fopen($fn . '.tmp', 'w');
1075          if (!$fh) return false;
1076          $ih = @fopen($fn . '.idx', 'r');
1077          if ($ih) {
1078              $ln = -1;
1079              while (($curline = fgets($ih)) !== false) {
1080                  fwrite($fh, (++$ln == $id) ? $line : $curline);
1081              }
1082              if ($id > $ln) {
1083                  while ($id > ++$ln)
1084                      fwrite($fh, "\n");
1085                  fwrite($fh, $line);
1086              }
1087              fclose($ih);
1088          } else {
1089              $ln = -1;
1090              while ($id > ++$ln)
1091                  fwrite($fh, "\n");
1092              fwrite($fh, $line);
1093          }
1094          fclose($fh);
1095          if ($conf['fperm'])
1096              chmod($fn . '.tmp', $conf['fperm']);
1097          io_rename($fn . '.tmp', $fn . '.idx');
1098          return true;
1099      }
1100  
1101      /**
1102       * Retrieve or insert a value in the index.
1103       *
1104       * @param string    $idx    name of the index
1105       * @param string    $suffix subpart identifier
1106       * @param string    $value  line to find in the index
1107       * @return int|bool          line number of the value in the index or false if writing the index failed
1108       *
1109       * @author Tom N Harris <tnharris@whoopdedo.org>
1110       */
1111      protected function addIndexKey($idx, $suffix, $value)
1112      {
1113          $index = $this->getIndex($idx, $suffix);
1114          $id = array_search($value, $index, true);
1115          if ($id === false) {
1116              $id = count($index);
1117              $index[$id] = $value;
1118              if (!$this->saveIndex($idx, $suffix, $index)) {
1119                  trigger_error("Failed to write $idx index", E_USER_ERROR);
1120                  return false;
1121              }
1122          }
1123          return $id;
1124      }
1125  
1126      /**
1127       * Get the list of lengths indexed in the wiki.
1128       *
1129       * Read the index directory or a cache file and returns
1130       * a sorted array of lengths of the words used in the wiki.
1131       *
1132       * @author YoBoY <yoboy.leguesh@gmail.com>
1133       *
1134       * @return array
1135       */
1136      protected function listIndexLengths()
1137      {
1138          return idx_listIndexLengths();
1139      }
1140  
1141      /**
1142       * Get the word lengths that have been indexed.
1143       *
1144       * Reads the index directory and returns an array of lengths
1145       * that there are indices for.
1146       *
1147       * @author YoBoY <yoboy.leguesh@gmail.com>
1148       *
1149       * @param array|int $filter
1150       * @return array
1151       */
1152      protected function indexLengths($filter)
1153      {
1154          global $conf;
1155          $idx = [];
1156          if (is_array($filter)) {
1157              // testing if index files exist only
1158              $path = $conf['indexdir'] . "/i";
1159              foreach (array_keys($filter) as $key) {
1160                  if (file_exists($path . $key . '.idx'))
1161                      $idx[] = $key;
1162              }
1163          } else {
1164              $lengths = idx_listIndexLengths();
1165              foreach ($lengths as $length) {
1166                  // keep all the values equal or superior
1167                  if ((int)$length >= (int)$filter)
1168                      $idx[] = $length;
1169              }
1170          }
1171          return $idx;
1172      }
1173  
1174      /**
1175       * Insert or replace a tuple in a line.
1176       *
1177       * @author Tom N Harris <tnharris@whoopdedo.org>
1178       *
1179       * @param string $line
1180       * @param string|int $id
1181       * @param int    $count
1182       * @return string
1183       */
1184      protected function updateTuple($line, $id, $count)
1185      {
1186          if ($line != '') {
1187              $line = preg_replace('/(^|:)' . preg_quote($id, '/') . '\*\d*/', '', $line);
1188          }
1189          $line = trim($line, ':');
1190          if ($count) {
1191              if ($line) {
1192                  return "$id*$count:" . $line;
1193              } else {
1194                  return "$id*$count";
1195              }
1196          }
1197          return $line;
1198      }
1199  
1200      /**
1201       * Split a line into an array of tuples.
1202       *
1203       * @author Tom N Harris <tnharris@whoopdedo.org>
1204       * @author Andreas Gohr <andi@splitbrain.org>
1205       *
1206       * @param array $keys
1207       * @param string $line
1208       * @return array
1209       */
1210      protected function parseTuples(&$keys, $line)
1211      {
1212          $result = [];
1213          if ($line == '') return $result;
1214          $parts = explode(':', $line);
1215          foreach ($parts as $tuple) {
1216              if ($tuple === '') continue;
1217              [$key, $cnt] = explode('*', $tuple);
1218              if (!$cnt) continue;
1219              if (isset($keys[$key])) {
1220                  $key = $keys[$key];
1221                  if ($key === false || is_null($key)) continue;
1222              }
1223              $result[$key] = $cnt;
1224          }
1225          return $result;
1226      }
1227  
1228      /**
1229       * Sum the counts in a list of tuples.
1230       *
1231       * @author Tom N Harris <tnharris@whoopdedo.org>
1232       *
1233       * @param string $line
1234       * @return int
1235       */
1236      protected function countTuples($line)
1237      {
1238          $freq = 0;
1239          $parts = explode(':', $line);
1240          foreach ($parts as $tuple) {
1241              if ($tuple === '') continue;
1242              [/* pid */, $cnt] = explode('*', $tuple);
1243              $freq += (int)$cnt;
1244          }
1245          return $freq;
1246      }
1247  }