<?php
/**
* SeekQuarry/Yioop --
* Open Source Pure PHP Search Engine, Crawler, and Indexer
*
* Copyright (C) 2009 - 2026 Chris Pollett chris@pollett.org
*
* LICENSE:
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 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 more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*
* END LICENSE
*
* @author Chris Pollett chris@pollett.org
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\tests;
use seekquarry\yioop\library\CrawlConstants as CC;
use seekquarry\yioop\library\index_bundle_iterators\IndexBundleIterator;
use seekquarry\yioop\library\index_bundle_iterators\UnionIterator;
use seekquarry\yioop\library\UnitTest;
/**
* UnionIteratorTest checks UnionIterator's merge of the documents its
* iterators find.
*/
class UnionIteratorTest extends UnitTest
{
/**
* setUp has nothing to make; each case makes its own iterators.
*/
public function setUp()
{
}
/**
* tearDown has nothing to remove.
*/
public function tearDown()
{
}
/**
* exhaustedIteratorIsSkippedTestCase unions an iterator whose two
* documents fill the block with one that has none left. Once the block
* is full, each later iterator's position was compared with every
* document as a (generation, offset) pair, and an exhausted iterator's
* -1 gave the warning "Trying to access array offset on int" in
* genDocOffsetCmp, logged 98 times on yioop.com between 26 and 30
* September.
*/
public function exhaustedIteratorIsSkippedTestCase()
{
$found = new UnionStubIterator([[0, 1], [0, 2]]);
$exhausted = new UnionStubIterator([]);
/* UnionIterator orders its iterators by how many documents they
claim; claiming more puts the exhausted one after the full
block, where the comparison was. */
$exhausted->num_docs = 10;
$union = new UnionIterator([$found, $exhausted], "stub");
$union->results_per_block = 2;
$warnings = [];
set_error_handler(function ($number, $message) use (&$warnings) {
$warnings[] = $message;
return true;
});
$pages = $union->findDocsWithWord();
restore_error_handler();
$this->assertEqual($warnings, [],
"an exhausted iterator gives no warning");
$this->assertEqual(is_array($pages) ? count($pages) : 0, 2,
"both documents of the other iterator are found");
}
/**
* partThatDoesNotAdvanceStepsOnTestCase unions a short list, which
* fills the block's two accumulators, with a part whose advance to a
* given document does not move. Asking it again and again is how a
* query can run forever; the union must step the part on by one
* document instead, so the part is asked to advance to a document
* only a few times, and the block still holds both documents.
*/
public function partThatDoesNotAdvanceStepsOnTestCase()
{
$short = new UnionStubIterator([[0, 1], [0, 5]]);
$stuck = new UnionStuckStubIterator([[0, 2], [0, 3], [0, 7]]);
$union = new UnionIterator([$short, $stuck], "stub");
$union->results_per_block = 2;
$pages = $union->findDocsWithWord();
$this->assertTrue($stuck->target_calls < 10,
"the part was asked to advance " . $stuck->target_calls .
" times, not again and again");
$this->assertEqual(is_array($pages) ? count($pages) : 0, 2,
"both documents of the short list are in the block");
}
/**
* sharedDocumentIsCountedOnceTestCase unions two iterators that both
* find the document at offset (0, 1), with room in the block for every
* document. The later iterator adds its relevance to that document's
* accumulator. It must then move on: left where it was, it offered
* the same document again as a new one, and its rank and relevance
* were counted twice. The first iterator's document at (0, 3), after
* the end of the later list, must also stay in the block.
*/
public function sharedDocumentIsCountedOnceTestCase()
{
$first = new UnionStubIterator([[0, 1], [0, 3]]);
$later = new UnionStubIterator([[0, 1], [0, 2]]);
$later->num_docs = 10;
$union = new UnionIterator([$first, $later], "stub");
$union->results_per_block = 10;
$pages = $union->findDocsWithWord();
$shared = $pages["doc0-1"] ?? [];
$this->assertEqual(is_array($pages) ? count($pages) : 0, 3,
"the three documents are found");
$this->assertEqual($shared[CC::RELEVANCE] ?? 0, 2,
"the shared document has the relevance of both iterators");
$this->assertEqual($shared[CC::DOC_RANK] ?? 0, 1,
"and its rank once");
}
/**
* partsAreTakenShortestFirstTestCase checks that a UnionIterator takes
* its parts shortest posting list first, as term at a time query
* processing takes its terms. Three parts of 2, 1 and 3 documents
* were left in that order.
*/
public function partsAreTakenShortestFirstTestCase()
{
$middle = new UnionStubIterator([[0, 1], [0, 2]]);
$shortest = new UnionStubIterator([[0, 1]]);
$longest = new UnionStubIterator([[0, 1], [0, 2], [0, 3]]);
$union = new UnionIterator([$middle, $shortest, $longest], "stub");
$this->assertTrue($union->index_bundle_iterators[0] === $shortest &&
$union->index_bundle_iterators[1] === $middle &&
$union->index_bundle_iterators[2] === $longest,
"parts go shortest posting list first");
}
/**
* joinedWordOpensAccumulatorsTestCase unions a part for tik and tok,
* whose two documents fill a block of two, with a longer part for
* tiktok holding an earlier document of its own. The tiktok part
* holds a word of the first part, so it may still open new
* accumulators, and its document is found. Given no words, the
* union does not know the part is joined, and the document stays
* out.
*/
public function joinedWordOpensAccumulatorsTestCase()
{
$split = new UnionStubIterator([[0, 2], [0, 3]]);
$joined = new UnionStubIterator([[0, 1], [0, 2], [0, 4]]);
$union = new UnionIterator([$split, $joined], "stub",
[["tik", "tok"], ["tiktok"]]);
$union->results_per_block = 2;
$this->assertEqual($union->joined_word_parts, [1],
"the tiktok part is noted as joined");
$pages = $union->findDocsWithWord();
$this->assertTrue(isset($pages["doc0-1"]),
"the document only the tiktok part has is found");
$split->reset();
$joined->reset();
$union = new UnionIterator([$split, $joined], "stub");
$union->results_per_block = 2;
$pages = $union->findDocsWithWord();
$this->assertTrue(!isset($pages["doc0-1"]),
"without the words it stays out");
}
/**
* thresholdKeepsExpectedNewAccumulatorsUnderQuotaTestCase gives a
* part 15 postings read of 30, five at each of relevance steps 10, 20
* and 30, and 7 new accumulators left. The rest of the list is
* expected to hold as many postings again, so five more reach step
* 30 and ten more reach step 20. Only step 30 keeps the expected
* number under 7.
*/
public function thresholdKeepsExpectedNewAccumulatorsUnderQuotaTestCase()
{
$short = new UnionStubIterator([[0, 1]]);
$long = new UnionStubIterator([[0, 1]]);
$long->num_docs = 30;
$union = new UnionIterator([$short, $long], "stub");
$union->postings_seen[1] = 15;
$union->relevance_counts[1] = [10 => 5, 20 => 5, 30 => 5];
$union->workOutThreshold(1, 7);
$this->assertEqual($union->thresholds[1], 30,
"the threshold is step 30");
}
/**
* recrawledDocumentIsCountedOnceTestCase unions a word's field key and
* own key over a page crawled twice, in partitions 0 and 6. Each key
* holds a posting for each copy, and WordIterator gives both postings
* the key of the latest copy. The union added the two copies' rank and
* relevance, so the page scored as two pages; a song page on yioop.com
* outranked yahoo.com for the query yahoo this way. The page must
* have its relevance from the two keys once, and its rank once.
*/
public function recrawledDocumentIsCountedOnceTestCase()
{
$field = new UnionStubIterator([[0, 1], [6, 2]], ["song", "song"]);
$own = new UnionStubIterator([[0, 1], [0, 5], [6, 2]],
["song", "other", "song"]);
$union = new UnionIterator([$field, $own], "stub");
$union->results_per_block = 10;
$pages = $union->findDocsWithWord();
$song = $pages["song"] ?? [];
$this->assertEqual(is_array($pages) ? count($pages) : 0, 2,
"the song page and the other page are found");
$this->assertEqual($song[CC::RELEVANCE] ?? 0, 2,
"the song page has the relevance of both keys once");
$this->assertEqual($song[CC::DOC_RANK] ?? 0, 1,
"and its rank once");
}
}
/**
* UnionStubIterator hands UnionIteratorTest a fixed list of documents, one
* at a time, as a word's iterator would.
*/
class UnionStubIterator extends IndexBundleIterator
{
/**
* The (generation, offset) pairs of the documents, in order
* @var array
*/
public $offsets;
/**
* Index in $offsets of the current document
* @var int
*/
public $position = 0;
/**
* Keys of the documents at $offsets, where they are not made from the
* offset
* @var array
*/
public $keys;
/**
* Makes an iterator over the documents at $offsets.
*
* @param array $offsets (generation, offset) pairs, in order
* @param array $keys the documents' keys, in the same order; a
* document without one is keyed by its offset
*/
public function __construct($offsets, $keys = [])
{
$this->offsets = $offsets;
$this->keys = $keys;
$this->num_docs = count($offsets);
}
/**
* Goes back to the first document.
*/
public function reset()
{
$this->position = 0;
}
/**
* Moves to the next document, or to the first at or after
* $gen_doc_offset when one is given.
*
* @param array $gen_doc_offset a (generation, offset) pair, or null
*/
public function advance($gen_doc_offset = null)
{
$this->position++;
while ($gen_doc_offset !== null &&
isset($this->offsets[$this->position]) &&
$this->genDocOffsetCmp($this->offsets[$this->position],
$gen_doc_offset) < 0) {
$this->position++;
}
}
/**
* Gives the current document's (generation, offset) pair, or -1 when
* none is left.
*
* @return mixed the pair, or -1
*/
public function currentGenDocOffsetWithWord()
{
return $this->offsets[$this->position] ?? -1;
}
/**
* Gives the current document as the one page found, or -1 when none
* is left.
*
* @return mixed the page keyed by its key, or -1
*/
public function findDocsWithWord()
{
$offset = $this->offsets[$this->position] ?? null;
if ($offset === null) {
return -1;
}
$key = $this->keys[$this->position] ?? "doc" . implode("-", $offset);
return [$key => [CC::KEY => $key, CC::DOC_RANK => 1,
CC::RELEVANCE => 1, CC::SCORE => 2, CC::IS_DOC => true,
CC::GENERATION => $offset[0]]];
}
}
/**
* UnionStuckStubIterator is a UnionStubIterator whose advance to a
* given document does not move, the first STUCK_CALLS times it is asked,
* as a word's iterator that fails to find a later posting would. It counts
* those asks, so UnionIteratorTest can see whether the union kept asking.
*/
class UnionStuckStubIterator extends UnionStubIterator
{
/**
* How many asks to advance to a given document are left unmoved before
* the iterator moves as UnionStubIterator does
*/
const STUCK_CALLS = 1000;
/**
* $target_calls counts the asks to advance to a given document
* @var int
*/
public $target_calls = 0;
/**
* advance moves to the next document when no document is given. When
* one is given, it stays where it is for the first STUCK_CALLS asks,
* then moves as UnionStubIterator does.
*
* @param array $gen_doc_offset a (generation, offset) pair, or null
*/
public function advance($gen_doc_offset = null)
{
if ($gen_doc_offset !== null) {
$this->target_calls++;
if ($this->target_calls <= self::STUCK_CALLS) {
return;
}
}
parent::advance($gen_doc_offset);
}
}
- Yioop Repo - Seekquarry