<?php

/*

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

 * Copyright (C) 2006-2009 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.

 */

/**

 * In Enano versions prior to 1.0.2, this class provided a search function that was keyword-based and allowed boolean searches. It was

 * cut from Coblynau and replaced with perform_search(), later in this file, because of speed issues. Now mostly deprecated. The only

 * thing remaining is the buildIndex function, which is still used by the path manager and the new search framework.

 *

 * @package Enano

 * @subpackage Page management frontend

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

 */

class Searcher

{

  var $results;

  var $index;

  var $warnings;

  var $match_case = false;

  function buildIndex($texts)

  {

    $this->index = Array();

    $stopwords = get_stopwords();

    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) < 2 || in_array($w, $stopwords) || strlen($w) > 63 || preg_match('/[\']{2,}/', $w))

          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]);

    }

  }

}

/**

 * Searches the site for the specified string and returns an array with each value being an array filled with the following:

 *   page_id: string, self-explanatory

 *   namespace: string, self-explanatory

 *   page_length: integer, the length of the full page in bytes

 *   page_text: string, the contents of the page (trimmed to ~150 bytes if necessary)

 *   score: numerical relevance score, 1-100, rounded to 2 digits and calculated based on which terms were present and which were not

 * @param string Search query

 * @param string|reference Will be filled with any warnings encountered whilst parsing the query

 * @param bool Case sensitivity - defaults to false

 * @param array|reference Will be filled with the parsed list of words.

 * @return array

 */

function perform_search($query, &$warnings, $case_sensitive = false, &$word_list)

{

  global $db, $session, $paths, $template, $plugins; // Common objects

  global $lang;

  $warnings = array();

  //

  // STAGE 0: PARSE SEARCH QUERY

  // Identify all terms of the query. Separate between what is required and what is not, and what should be sent through the index as

  // opposed to straight-out LIKE-selected.

  //

  $query = parse_search_query($query, $warnings);

  // Segregate search terms containing spaces

  $query_phrase = array(

    'any' => array(),

    'req' => array()

    );

  foreach ( $query['any'] as $i => $_ )

  {

    $term =& $query['any'][$i];

    $term = trim($term);

    // the indexer only indexes words a-z with apostrophes

    if ( preg_match('/[^A-Za-z\']/', $term) )

    {

      $query_phrase['any'][] = $term;

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

    }

  }

  unset($term);

  $query['any'] = array_values($query['any']);

  foreach ( $query['req'] as $i => $_ )

  {

    $term =& $query['req'][$i];

    $term = trim($term);

    if ( preg_match('/[^A-Za-z\']/', $term) )

    {

      $query_phrase['req'][] = $term;

      unset($term, $query['req'][$i]);

    }

  }

  unset($term);

  $query['req'] = array_values($query['req']);

  $results = array();

  $scores = array();

  $ns_list = '(' . implode('|', array_keys($paths->nslist)) . ')';

  // FIXME: Update to use FULLTEXT algo when available.

  // Build an SQL query to load from the index table

  if ( count($query['any']) < 1 && count($query['req']) < 1 && count($query_phrase['any']) < 1 && count($query_phrase['req']) < 1 )

  {

    // This is both because of technical restrictions and devastation that would occur on shared servers/large sites.

    $warnings[] = $lang->get('search_err_query_no_positive');

    return array();

  }

  //

  // STAGE 1

  // Get all possible result pages from the search index. Tally which pages have the most words, and later sort them by boolean relevance

  //

  // Skip this if no indexable words are included

  if ( count($query['any']) > 0 || count($query['req']) > 0 )

  {

    $where_any = array();

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

    {

      $term = escape_string_like($term);

      if ( !$case_sensitive )

        $term = strtolower($term);

      $where_any[] = $term;

    }

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

    {

      $term = escape_string_like($term);

      if ( !$case_sensitive )

        $term = strtolower($term);

      $where_any[] = $term;

    }

    $col_word = ( $case_sensitive ) ? 'word' : 'word_lcase';

    $where_any_str = ( count($where_any) > 0 ) ? '( ' . $col_word . ' LIKE \'%' . implode('%\' OR ' . $col_word . ' LIKE \'%', $where_any) . '%\' )' : '';

    // generate query

    $sql = "SELECT word, page_names FROM " . table_prefix . "search_index WHERE {$where_any_str}";

    if ( !($q = $db->sql_query($sql)) )

      $db->_die('Error is in perform_search(), includes/search.php, query 1');

    $word_tracking = array();

    if ( $row = $db->fetchrow($q) )

    {

      do

      {

        // get page list

        $pages =& $row['page_names'];

        // Find page IDs that contain commas

        // This should never happen because commas are escaped by sanitize_page_id(). Nevertheless for compatibility with older

        // databases, and to alleviate the concerns of hackers, we'll accommodate for page IDs with commas here by checking for

        // IDs that don't match the pattern for stringified page ID + namespace. If it doesn't match, that means it's a continuation

        // of the previous ID and should be concatenated to the previous entry.

        $matches = strpos($pages, ',') ? explode(',', $pages) : array($pages);

        $prev = false;

        foreach ( $matches as $i => $_ )

        {

          $match =& $matches[$i];

          if ( !preg_match("/^ns=$ns_list;pid=(.+)$/", $match) && $prev )

          {

            $matches[$prev] .= ',' . $match;

            unset($match, $matches[$i]);

            continue;

          }

          $prev = $i;

        }

        unset($match);

        // Iterate through each of the results, assigning scores based on how many times the page has shown up.

        // This works because this phase of the search is strongly word-based not page-based. If a page shows up

        // multiple times while fetching the result rows from the search_index table, it simply means that page

        // contains more than one of the terms the user searched for.

        foreach ( $matches as $match )

        {

          $word_cs = (( $case_sensitive ) ? $row['word'] : strtolower($row['word']));

          if ( isset($word_tracking[$match]) && in_array($word_cs, $word_tracking[$match]) )

          {

            continue;

          }

          if ( isset($word_tracking[$match]) )

          {

            if ( isset($word_tracking[$match]) )

            {

              $word_tracking[$match][] = $word_cs;

            }

          }

          else

          {

            $word_tracking[$match] = array($word_cs);

          }

          // echo '<pre>' . print_r($word_tracking, true) . '</pre>';

          $inc = 1;

          // Is this search term present in the page's title? If so, give extra points

          preg_match("/^ns=$ns_list;pid=(.+)$/", $match, $piecesparts);

          $title = get_page_title_ns($piecesparts[2], $piecesparts[1]);

          $test_func = ( $case_sensitive ) ? 'strstr' : 'stristr';

          if ( $test_func($title, $row['word']) || $test_func($piecesparts[2], $row['word']) )

          {

            $inc = 1.5;

          }

          // increase points if 2 or more words match a phrase in the title

          for ( $i = 0; $i < count($where_any) - 1; $i++ )

          {

            $phrase = "{$where_any[$i]} {$where_any[$i + 1]}";

            if ( $test_func($title, $phrase) )

            {

              $inc *= 1.25;

            }

          }

          // Deduct points if there are few similarities between the words

          $lev_array = array();

          foreach ( $where_any as $qword )

          {

            if ( strstr($word_cs, $qword) )

              $lev_array[ $qword ] = levenshtein($qword, $word_cs);

          }

          if ( min($lev_array) > 3 )

          {

            $inc /= array_sum($lev_array) / count($lev_array);

          }

          if ( isset($scores[$match]) )

          {

            $scores[$match] = $scores[$match] + $inc;

          }

          else

          {

            $scores[$match] = $inc;

          }

        }

      }

      while ( $row = $db->fetchrow($q) );

    }

    $db->free_result($q);

    //

    // STAGE 2: FIRST ELIMINATION ROUND

    // Iterate through the list of required terms. If a given page is not found to have the required term, eliminate it

    //

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

    {

      foreach ( $word_tracking as $i => $page )

      {

        if ( !in_array($term, $page) )

        {

          unset($word_tracking[$i], $scores[$i]);

        }

      }

    }

  }

  //

  // STAGE 3: PHRASE SEARCHING

  // Use LIKE to find pages with specified phrases. We can do a super-picky single query without another elimination round because

  // at this stage we can search the full page_text column instead of relying on a word list.

  //

  // We can skip this stage if none of these special terms apply

  $text_col = ( $case_sensitive ) ? 'page_text' : ENANO_SQLFUNC_LOWERCASE . '(page_text)';

  $name_col = ( $case_sensitive ) ? 'name' : ENANO_SQLFUNC_LOWERCASE . '(name)';

  $text_col_join = ( $case_sensitive ) ? 't.page_text' : ENANO_SQLFUNC_LOWERCASE . '(t.page_text)';

  $name_col_join = ( $case_sensitive ) ? 'p.name' : ENANO_SQLFUNC_LOWERCASE . '(p.name)';

  $concat_column = ( ENANO_DBLAYER == 'MYSQL' ) ?

    'CONCAT(\'ns=\',t.namespace,\';pid=\',t.page_id)' :

    "'ns=' || t.namespace || ';pid=' || t.page_id";

  if ( count($query_phrase['any']) > 0 || count($query_phrase['req']) > 0 )

  {

    $where_any = array();

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

    {

      $term = escape_string_like($term);

      if ( !$case_sensitive )

        $term = strtolower($term);

      $where_any[] = "( $text_col LIKE '%$term%' OR $name_col LIKE '%$term%' )";

    }

    $where_any = ( count($where_any) > 0 ) ? implode(" OR\n  ", $where_any) : '';

    // Also do required terms, but use AND to ensure that all required terms are included

    $where_req = array();

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

    {

      $term = escape_string_like($term);

      if ( !$case_sensitive )

        $term = strtolower($term);

      $where_req[] = "( $text_col LIKE '%$term%' OR $name_col LIKE '%$term%' )";

    }

    $and_clause = ( $where_any != '' ) ? 'AND ' : '';

    $where_req = ( count($where_req) > 0 ) ? "{$and_clause}" . implode(" AND\n  ", $where_req) : '';

    $sql = 'SELECT ' . $concat_column . ' AS id, p.name, t.page_text FROM ' . table_prefix . "page_text AS t\n"

            . "  LEFT JOIN " . table_prefix . "pages AS p\n"

            . "    ON ( p.urlname = t.page_id AND p.namespace = t.namespace )\n"

            . "  WHERE p.visible = 1 AND (\n    $where_any\n    $where_req\n  );";

    if ( !($q = $db->sql_query($sql)) )

      $db->_die('Error is in perform_search(), includes/search.php, query 2. Parsed query dump follows:<pre>(indexable) ' . htmlspecialchars(print_r($query, true)) . '(non-indexable) ' . htmlspecialchars(print_r($query_phrase, true)) . '</pre>');

    if ( $row = $db->fetchrow() )

    {

      do

      {

        $id =& $row['id'];

        $inc = 0.0;

        $title = $row['name'];

        $test_func = ( $case_sensitive ) ? 'strstr' : 'stristr';

        // Is this search term present in the page's title? If so, give extra points

        $word_list = array_merge($query_phrase['any'], $query_phrase['req']);

        foreach ( $word_list as $word )

        {

          if ( $test_func($title, $word) )

            $inc += 1.5;

          else if ( $test_func($row['page_text'], $word) )

            $inc += 1.0;

        }

        // increase points if 2 or more words match a phrase in the title

        for ( $i = 0; $i < count($word_list) - 1; $i++ )

        {

          $phrase = "{$word_list[$i]} {$word_list[$i + 1]}";

          if ( $test_func($title, $phrase) )

            $inc *= 1.25;

          else if ( $test_func($row['page_text'], $phrase) )

            $inc *= 1.125;

        }

        if ( isset($scores[$id]) )

        {

          $scores[$id] = $scores[$id] + $inc;

        }

        else

        {

          $scores[$id] = $inc;

        }

      }

      while ( $row = $db->fetchrow() );

    }

    $db->free_result();

  }

  //

  // STAGE 4 - SELECT PAGE TEXT AND ELIMINATE NOTS

  // At this point, we have a complete list of all the possible pages. Now we want to obtain the page text, and within the same query

  // eliminate any terms that shouldn't be in there.

  //

  // Generate master word list for the highlighter

  $word_list = array_values(array_merge($query['any'], $query['req'], $query_phrase['any'], $query_phrase['req']));

  $text_where = array();

  foreach ( $scores as $page_id => $_ )

  {

    $text_where[] = $db->escape($page_id);

  }

  $text_where = '( ' . $concat_column . ' = \'' . implode('\' OR ' . $concat_column . ' = \'', $text_where) . '\' )';

  if ( count($query['not']) > 0 )

    $text_where .= ' AND';

  $where_not = array();

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

  {

    $term = escape_string_like($term);

    if ( !$case_sensitive )

      $term = strtolower($term);

    $where_not[] = $term;

  }

  $where_not = ( count($where_not) > 0 ) ? "$text_col NOT LIKE '%" . implode("%' AND $text_col NOT LIKE '%", $where_not) . "%'" : '';

  $sql = 'SELECT ' . $concat_column . ' AS id, t.page_id, t.namespace, CHAR_LENGTH(t.page_text) AS page_length, t.page_text, p.name AS page_name FROM ' . table_prefix . "page_text AS t

            LEFT JOIN " . table_prefix . "pages AS p

              ON ( p.urlname = t.page_id AND p.namespace = t.namespace )

            WHERE p.visible = 1 AND ( $text_where $where_not );";

  if ( !($q = $db->sql_unbuffered_query($sql)) )

    $db->_die('Error is in perform_search(), includes/search.php, query 3');

  $page_data = array();

  if ( $row = $db->fetchrow() )

  {

    do

    {

      $row['page_text'] = htmlspecialchars($row['page_text']);

      $row['page_name'] = htmlspecialchars($row['page_name']);

      // Highlight results (this is wonderfully automated)

      $row['page_text'] = highlight_and_clip_search_result($row['page_text'], $word_list, $case_sensitive);

      if ( strlen($row['page_text']) > 250 && !preg_match('/^\.\.\.(.+)\.\.\.$/', $row['page_text']) )

      {

        $row['page_text'] = substr($row['page_text'], 0, 150) . '...';

      }

      $row['page_name'] = highlight_search_result($row['page_name'], $word_list, $case_sensitive);

      $page_data[$row['id']] = $row;

    }

    while ( $row = $db->fetchrow() );

  }

  $db->free_result();

  //

  // STAGE 5 - SPECIAL PAGE TITLE SEARCH

  // Iterate through $paths->pages and check the titles for search terms. Score accordingly.

  //

  foreach ( $paths->pages as $id => $page )

  {

    if ( $page['namespace'] != 'Special' || $page['visible'] == 0 )

      continue;

    $idstring = 'ns=' . $page['namespace'] . ';pid=' . $page['urlname_nons'];

    $any = array_values(array_unique(array_merge($query['any'], $query_phrase['any'])));

    foreach ( $any as $term )

    {

      if ( $case_sensitive )

      {

        if ( strstr($page['name'], $term) || strstr($page['urlname_nons'], $term) )

        {

          ( isset($scores[$idstring]) ) ? $scores[$idstring] = $scores[$idstring] + 1.5 : $scores[$idstring] = 1.5;

        }

      }

      else

      {

        if ( stristr($page['name'], $term) || stristr($page['urlname_nons'], $term) )