<?php

/*

 * Enano - an open-source CMS capable of wiki functions, Drupal-like sidebar blocks, and everything in between

 * Copyright (C) 2006-2007 Dan Fuhry

 * search.php - algorithm used to search pages

 *

 * This program is Free Software; you can redistribute and/or modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied

 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for details.

 */

/**

 * Implementation of array_merge() that preserves key names. $arr2 takes precedence over $arr1.

 * @param array $arr1

 * @param array $arr2

 * @return array

 */

function enano_safe_array_merge($arr1, $arr2)

{

  $arr3 = $arr1;

  foreach($arr2 as $k => $v)

  {

    $arr3[$k] = $v;

  }

  return $arr3;

}

/**

 * Algorithm to actually do the searching. This system usually works pretty fast (tested and developed on a site with 22 pages) but one

 * caveat of this algorithm is that it has to load the entire index into memory. It also requires manual parsing of the search query

 * which can be quite CPU-intensive. On the flip side this algorithm is extremely flexible and can be adapted for other uses very easily.

 * 

 * Most of the time, this system is disabled. It is only used when MySQL can't or won't allow FULLTEXT indices.

 *

 * @package Enano

 * @subpackage Page management frontend

 * @license GNU General Public License http://www.enanocms.org/Special:GNU_General_Public_License

 */

class Searcher

{

  var $results;

  var $index;

  var $warnings;

  var $match_case = false;

  function __construct()

  {

    $this->warnings = Array();

  }

  function Searcher()

  {

    $this->__construct();

  }

  function warn($t)

  {

    if(!in_array($t, $this->warnings)) $this->warnings[] = $t;

  }

  function convertCase($text)

  {

    return ( $this->match_case ) ? $text : strtolower($text);

  }

  function buildIndex($texts)

  {

    $this->index = Array();

    foreach($texts as $i => $l)

    {

      $seed = md5(microtime(true) . mt_rand());

      $texts[$i] = str_replace("'", 'xxxApoS'.$seed.'xxx', $texts[$i]);

      $texts[$i] = preg_replace('#([\W_]+)#i', ' ', $texts[$i]);

      $texts[$i] = preg_replace('#([ ]+?)#', ' ', $texts[$i]);

      $texts[$i] = preg_replace('#([\']*){2,}#s', '', $texts[$i]);

      $texts[$i] = str_replace('xxxApoS'.$seed.'xxx', "'", $texts[$i]);

      $l = $texts[$i];

      $words = Array();

      $good_chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\' ';

      $good_chars = enano_str_split($good_chars, 1);

      $letters = enano_str_split($l, 1);

      foreach($letters as $x => $t)

      {

        if(!in_array($t, $good_chars))

          unset($letters[$x]);

      }

      $letters = implode('', $letters);

      $words = explode(' ', $letters);

      foreach($words as $c => $w)

      {

        if(strlen($w) < 4)

          unset($words[$c]);

        else

          $words[$c] = $w;

      }

      $words = array_values($words);

      foreach($words as $c => $w)

      {

        if(isset($this->index[$w]))

        {

          if(!in_array($i, $this->index[$w]))

            $this->index[$w][] = $i;

        }

        else

        {

          $this->index[$w] = Array();

          $this->index[$w][] = $i;

        }

      }

    }

    foreach($this->index as $k => $v)

    {

      $this->index[$k] = implode(',', $this->index[$k]);

    }

  }

  function search($query, $texts)

  {

    // OK, let's establish some basics here. Here is the procedure for performing the search:

    //   * search for items that matches all the terms in the correct order.

    //   * search for items that match in any order

    //   * eliminate one term and do the loop all over

    $this->results = Array();

    $query = $this->parseQuery($query);

    $querybak = $query;

    for($i = sizeof($query['any'])-1; $i >= 0; $i--)

    {

      $res = $this->performCoreSearch($query, $texts, true);

      $this->results = enano_safe_array_merge($this->results, $res);

      $res = $this->performCoreSearch($query, $texts, false);

      $this->results = enano_safe_array_merge($this->results, $res);

      unset($query['any'][$i]);

    }

    // Last resort - search for any of the terms instead of all of 'em

    $res = $this->performCoreSearch($querybak, $texts, false, true);

    $this->results = enano_safe_array_merge($this->results, $res);

    $this->highlightResults($querybak);

  }

  // $texts should be a textual MySQL query!

  // @todo document

  function searchMySQL($query, $texts)

  {

    global $db;

    // OK, let's establish some basics here. Here is the procedure for performing the search:

    //   * search for items that matches all the terms in the correct order.

    //   * search for items that match in any order

    //   * eliminate one term and do the loop all over

    $this->results = Array();

    $query = $this->parseQuery($query);

    $querytmp = $query;

    $querybak = $query;

    for($i = sizeof($querytmp['any'])-1; $i >= 0; $i--)

    {

      $res = $this->performCoreSearchMySQL($querytmp, $texts, true);

      $this->results = enano_safe_array_merge($this->results, $res);

      $res = $this->performCoreSearchMySQL($querytmp, $texts, false);

      $this->results = enano_safe_array_merge($this->results, $res);

      unset($querytmp['any'][$i]);

    }

    // Last resort - search for any of the terms instead of all of 'em

    $res = $this->performCoreSearchMySQL($querybak, $texts, false, true);

    $this->results = enano_safe_array_merge($this->results, $res);

    $this->highlightResults($querybak);

  }

  /**

   * This method assumes that $query is already parsed and $texts is an (associative) array of possible results

   * @param array $query A search query parsed with Searcher::parseQuery()

   * @param array $texts The list of possible results

   * @param bool $exact_order If true, only matches results with the terms in the same order as the terms in the query

   * @return array An associative array of results

   * @access private

   */

  function performCoreSearch($query, $texts, $exact_order = false, $any = false)

  {

    $textkeys = array_keys($texts);

    $results = Array();

    if($exact_order)

    {

      $query = $this->concatQueryTerms($query);

    }

    $query['trm'] = array_merge($query['any'], $query['req']);

    # Find all remotely possible results first

    // Single-word terms

    foreach($this->index as $term => $keys)

    {

      foreach($query['trm'] as $userterm)

      {

        if($this->convertCase($userterm) == $this->convertCase($term))

        {

          $k = explode(',', $keys);

          foreach($k as $idxkey)

          {

            if(isset($texts[$idxkey])) 

            {

              $results[$idxkey] = $texts[$idxkey];

            }

            else

            {

              if(preg_match('#^([0-9]+)$#', $idxkey))

              {

                $idxkey = intval($idxkey);

                if(isset($texts[$idxkey])) $results[$idxkey] = $texts[$idxkey];

              }

            }

          }

        }

      }

    }

    // Quoted terms

    foreach($query['trm'] as $userterm)

    {

      if(!preg_match('/[\s"\'~`!@#\$%\^&\*\(\)\{\}:;<>,.\/\?_-]/', $userterm)) continue;

      foreach($texts as $k => $t)

      {

        if(strstr($this->convertCase($t), $this->convertCase($userterm)))

        {

          // We have a match!

          if(!isset($results[$k])) $results[$k] = $t;

        }

      }

    }

    // Remove excluded terms

    foreach($results as $k => $r)

    {

      foreach($query['not'] as $not)

      {

        if(strstr($this->convertCase($r), $this->convertCase($not))) unset($results[$k]);

      }

    }

    if(!$any)

    {

      // Remove results not containing all terms

      foreach($results as $k => $r)

      {

        foreach($query['any'] as $term)

        {

          if(!strstr($this->convertCase($r), $this->convertCase($term))) unset($results[$k]);

        }

      }

    }

    // Remove results not containing all required terms

    foreach($results as $k => $r)

    {

      foreach($query['req'] as $term)

      {

        if(!strstr($this->convertCase($r), $this->convertCase($term))) unset($results[$k]);

      }

    }

    return $results;

  }

  /**

   * This is the same as performCoreSearch, but $texts should be a MySQL result resource. This can save tremendous amounts of memory on large sites.

   * @param array $query A search query parsed with Searcher::parseQuery()

   * @param string $texts A text MySQL query that selects the text as the first column and the index key as the second column

   * @param bool $exact_order If true, only matches results with the terms in the same order as the terms in the query

   * @return array An associative array of results

   * @access private

   */

  function performCoreSearchMySQL($query, $texts, $exact_order = false, $any = false)

  {

    global $db;

    $results = Array();

    if($exact_order)

    {

      $query = $this->concatQueryTerms($query);

    }

    $query['trm'] = array_merge($query['any'], $query['req']);

    # Find all remotely possible results first

    $texts = $db->sql_query($texts);

    if ( !$texts )

      $db->_die('The error is in the search engine.');

    if ( $r = $db->fetchrow_num($texts) )

    {

      do

      {

        foreach($this->index as $term => $keys)

        {

          foreach($query['trm'] as $userterm)

          {

            if($this->convertCase($userterm) == $this->convertCase($term))

            {

              $k = explode(',', $keys);

              foreach($k as $idxkey)

              {

                $row[0] = $r[0];

                $row[1] = $r[1];

                if(!isset($row[1]))

                {

                  echo('PHP PARSER BUG: $row[1] is set but not set... includes/search.php:'.__LINE__);

                  $GLOBALS['template']->footer();

                  exit;

                }

                if($row[1] == $idxkey)

                  $results[$idxkey] = $row[0];

                else

                {

                  if(preg_match('#^([0-9]+)$#', $idxkey))

                  {

                    $idxkey = intval($idxkey);

                    if($row[1] == $idxkey) $results[$idxkey] = $row[0];

                  }

                }

              }

            }

          }

        }

        // Quoted terms

        foreach($query['trm'] as $userterm)

        {

          if(!preg_match('/[\s"\'~`!@#\$%\^&\*\(\)\{\}:;<>,.\/\?_-]/', $userterm)) continue;

          if(strstr($this->convertCase($r[0]), $this->convertCase($userterm)))

          {

            // We have a match!

            if(!isset($results[$r[1]])) $results[$r[1]] = $r[0];

          }

        }

      } while( $r = $db->fetchrow_num($texts) );

    }

    // Remove excluded terms

    foreach($results as $k => $r)

    {

      foreach($query['not'] as $not)

      {

        if(strstr($this->convertCase($r), $this->convertCase($not))) unset($results[$k]);

      }

    }

    if(!$any)

    {

      // Remove results not containing all terms

      foreach($results as $k => $r)

      {

        foreach($query['any'] as $term)

        {

          if(!strstr($this->convertCase($r), $this->convertCase($term))) unset($results[$k]);

        }

      }

    }

    // Remove results not containing all terms

    foreach($results as $k => $r)

    {

      foreach($query['req'] as $term)

      {

        if(!strstr($this->convertCase($r), $this->convertCase($term))) unset($results[$k]);

      }

    }

    return $results;

  }

  function concatQueryTerms($query)

  {

    $tmp = implode(' ', $query['any']);

    unset($query['any']);

    $query['any'] = Array(0 => $tmp);

    return $query;

  }

  /**

   * Builds a basic assoc array with a more organized version of the query

   */

  function parseQuery($query)

  {

    $ret = array(

      'any' => array(),

      'req' => array(),

      'not' => array()

      );

    $terms = array();

    $in_quote = false;

    $start_term = 0;

    $just_finished = false;

    for ( $i = 0; $i < strlen($query); $i++ )

    {

      $chr = $query{$i};

      $prev = ( $i > 0 ) ? $query{ $i - 1 } : '';

      $next = ( ( $i + 1 ) < strlen($query) ) ? $query{ $i + 1 } : '';

      if ( ( $chr == ' ' && !$in_quote ) || ( $i + 1 == strlen ( $query ) ) )

      {

        $len = ( $next == '' ) ? $i + 1 : $i - $start_term;

        $word = substr ( $query, $start_term, $len );

        $terms[] = $word;

        $start_term = $i + 1;

      }

      elseif ( $chr == '"' && $in_quote && $prev != '\\' )

      {

        $word = substr ( $query, $start_term, $i - $start_term + 1 );

        $start_pos = ( $next == ' ' ) ? $i + 2 : $i + 1;

        $in_quote = false;

      }

      elseif ( $chr == '"' && !$in_quote )

      {

        $in_quote = true;

        $start_pos = $i;

      }

    }

    $ticker = 0;

    foreach ( $terms as $element => $__unused )

    {

      $atom =& $terms[$element];

      $ticker++;

      if ( $ticker == 20 )

      {

        $this->warn('Some of your search terms were excluded because searches are limited to 20 terms to prevent excessive server load.');

        break;

      }

      if ( substr ( $atom, 0, 2 ) == '+"' && substr ( $atom, ( strlen ( $atom ) - 1 ), 1 ) == '"' )

      {

        $word = substr ( $atom, 2, ( strlen( $atom ) - 3 ) );

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['req']))

        {

          $this->warn('One or more of your search terms was excluded because duplicate terms were encountered.');

          $ticker--;

          continue;

        }

        $ret['req'][] = $word;

      }

      elseif ( substr ( $atom, 0, 2 ) == '-"' && substr ( $atom, ( strlen ( $atom ) - 1 ), 1 ) == '"' )

      {

        $word = substr ( $atom, 2, ( strlen( $atom ) - 3 ) );

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['not']))

        {

          $this->warn('One or more of your search terms was excluded because duplicate terms were encountered.');

          $ticker--;

          continue;

        }

        $ret['not'][] = $word;

      }

      elseif ( substr ( $atom, 0, 1 ) == '+' )

      {

        $word = substr ( $atom, 1 );

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['req']))

        {

          $this->warn('One or more of your search terms was excluded because duplicate terms were encountered.');

          $ticker--;

          continue;

        }

        $ret['req'][] = $word;

      }

      elseif ( substr ( $atom, 0, 1 ) == '-' )

      {

        $word = substr ( $atom, 1 );

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['not']))

        {

          $this->warn('One or more of your search terms was excluded because duplicate terms were encountered.');

          $ticker--;

          continue;

        }

        $ret['not'][] = $word;

      }

      elseif ( substr ( $atom, 0, 1 ) == '"' && substr ( $atom, ( strlen($atom) - 1 ), 1 ) == '"' )

      {

        $word = substr ( $atom, 1, ( strlen ( $atom ) - 2 ) );

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['any']))

        {

          $this->warn('One or more of your search terms was excluded because duplicate terms were encountered.');

          $ticker--;

          continue;

        }

        $ret['any'][] = $word;

      }

      else

      {

        $word = $atom;

        if ( strlen ( $word ) < 4 )

        {

          $this->warn('One or more of your search terms was excluded because terms must be at least 4 characters in length.');

          $ticker--;

          continue;

        }

        if(in_array($word, $ret['any']))

        {