<?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
*
* This file contains unit tests of the IndexDocumentBundleTable class
*
* @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\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\models\Model;
use seekquarry\yioop\library\CrawlConstants as CC;
use seekquarry\yioop\library\storage_formats\IndexDocumentBundle;
use seekquarry\yioop\library\IndexManager;
use seekquarry\yioop\library\UnitTest;
use seekquarry\yioop\library\index_bundle_iterators\GroupIterator;
use seekquarry\yioop\library\index_bundle_iterators\IntersectIterator;
use seekquarry\yioop\library\index_bundle_iterators\UnionIterator;
use seekquarry\yioop\library\index_bundle_iterators\WordIterator;
/**
* WordIteratorTest checks WordIterator, which walks the documents of an
* IndexDocumentBundle that hold one word, and IntersectIterator, which
* joins such walks to find the documents holding several words.
*/
class WordIteratorTest extends UnitTest
{
/**
* Name of IndexDocumentBundle used to store test documents
*/
const TEST_BUNDLE = "IndexData200000000";
/**
* Prefix of folders for index manager test
*/
const TEST_DIR = __DIR__ . '/test_files/word_iterator_test';
/**
* $index_archive is the IndexDocumentBundle that setUp makes for the
* cases to add their test pages to.
* @var object
*/
public $index_archive;
/**
* setUp makes the test folder if it is missing and opens a new
* IndexDocumentBundle in it, which each case then fills with pages.
*/
public function setUp()
{
IndexDocumentBundle::$temp_folder = C\TEST_DIR . "/test_files";
$test_bundle = self::TEST_BUNDLE;
if (!file_exists(self::TEST_DIR)) {
mkdir(self::TEST_DIR);
}
$this->index_archive = new IndexDocumentBundle(self::TEST_DIR .
"/$test_bundle", false, "TestBundle", 100, 101);
}
/**
* tearDown deletes the test folder and every bundle a case made in it,
* so the next case starts from an empty folder.
*/
public function tearDown()
{
array_map("unlink", glob(C\TEST_DIR .
"/test_files/signal_totals_*") ?: []);
IndexDocumentBundle::$temp_folder = C\TEMP_DIR;
$model = new Model();
$model->db->unlinkRecursive(self::TEST_DIR);
}
/**
* findTermTestCase stores 10 pages in the bundle. The word be is on
* every page, and each of the words or0 to or9 is on one page. The case
* checks that a WordIterator's currentDocsWithWord gives 10 pages for
* be and 1 page for each of the others.
*/
public function findTermTestCase()
{
IndexManager::clearCache();
$index_archive = $this->index_archive;
$dictionary = $index_archive->dictionary;
$keys = [];
for ($i = 0; $i < 10; $i++) {
$keys[$i] = $this->docidFromIntKeys($i, $i, $i);
$docs[] = [
CC::DOC_ID => $keys[$i],
CC::SUMMARY =>
[
CC::DESCRIPTION => "to$i be or$i not$i to$i be...",
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => "Some$i Shakespeare$i Play$i",
CC::URL => "https://www.somewhere$i.com/"
],
CC::PAGE => "Page $i",
];
}
$num_docs = count($docs);
$index_archive->addPages($docs, $num_docs);
$index_archive->updateDictionary();
$index_archive->forceSave();
$word_iterator = new WordIterator(L\canonicalTerm("be"),
self::TEST_DIR . "/" . self::TEST_BUNDLE, true, null, 10);
$current_doc_with_word = $word_iterator->currentDocsWithWord();
$current_doc_with_word = (is_array($current_doc_with_word)) ?
$current_doc_with_word : [];
$this->assertEqual(count($current_doc_with_word), 10,
"Number of occurrences of 'be' correct");
for ($i = 0; $i < 10; $i++) {
$word_iterator = new WordIterator(L\canonicalTerm("or$i"),
self::TEST_DIR . "/". self::TEST_BUNDLE, true, null, 10);
$current_doc_with_word = $word_iterator->currentDocsWithWord();
$current_doc_with_word = (is_array($current_doc_with_word)) ?
$current_doc_with_word : [];
$this->assertEqual(count($current_doc_with_word), 1,
"Number of occurrences of 'or$i' correct");
}
}
/**
* joinFindsDocumentAfterPartitionChangeTestCase checks that joining two
* words finds a document in a later partition when one word's walk had
* to leave an earlier partition to catch up with the other. Partitions
* hold four pages: in the first, beta is on the first and fourth and
* alpha on the second. The second partition's
* first page holds both words, and it is the only page that does, so
* the join of alpha and beta must find it. Before the walk forgot the
* last partition's document index on moving on, alpha reported itself
* past that page and the join ended with nothing.
*/
public function joinFindsDocumentAfterPartitionChangeTestCase()
{
IndexManager::clearCache();
$bundle_path = self::TEST_DIR . "/IndexData200000001";
$index_archive = new IndexDocumentBundle($bundle_path, false,
"TestBundle", 4, 5);
$descriptions = ["beta", "alpha", "gamma", "beta", "alpha beta",
"gamma", "gamma", "gamma", "gamma", "gamma"];
$docs = [];
foreach ($descriptions as $i => $description) {
$docs[] = [
CC::DOC_ID => $this->docidFromIntKeys($i, $i, $i),
CC::SUMMARY => [
CC::DESCRIPTION => $description,
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => "Page$i",
CC::URL => "https://www.somewhere$i.com/"],
CC::PAGE => "Page $i"];
}
$index_archive->addPages($docs, count($docs));
$index_archive->updateDictionary();
$index_archive->forceSave();
$iterators = [];
foreach (["alpha", "beta"] as $word) {
$iterators[] = new WordIterator(L\canonicalTerm($word),
$bundle_path, true, null, 10);
}
$join = new IntersectIterator($iterators, [0, 1]);
$found = $join->currentDocsWithWord();
$found = is_array($found) ? $found : [];
$this->assertEqual(count($found), 1,
"the join of alpha and beta finds the one page holding both");
}
/**
* BATCH_PAGES_PER_PARTITION is how many pages go into each partition
* of the bundle batchesReachEveryPartitionTestCase builds.
*/
const BATCH_PAGES_PER_PARTITION = 2;
/**
* BATCH_ROWS is how many dictionary rows, one a partition, the word
* iterators of batchesReachEveryPartitionTestCase read in one batch.
*/
const BATCH_ROWS = 2;
/**
* BATCH_PARTITIONS is how many partitions batchesReachEveryPartition
* TestCase fills. The last is the active one, so a word on every
* partition has three dictionary rows: one full batch of BATCH_ROWS,
* then a batch of one row that the active partition's row fills.
*/
const BATCH_PARTITIONS = 4;
/**
* batchesReachEveryPartitionTestCase checks that a word in more
* partitions than one batch of dictionary rows holds is read in every
* partition, alone and in a join. BATCH_PARTITIONS partitions of
* BATCH_PAGES_PER_PARTITION pages are read BATCH_ROWS rows at a
* time, rather than NUM_DISTINCT_GENERATIONS. The made-up word zorp
* is on every even page, and the made-up word quib is on two of
* those, one in the first partition and one in the last; common
* English words would be dropped as stop words. A walk of zorp must
* reach every page it is on, and the join of zorp and quib must find
* both pages. Before the active partition's row was kept out of all
* but a word's last batch, a walk went from the first batch to the
* active partition and never read the partitions between. Before a
* batch holding the active partition's row was taken as the word's
* last, a batch that row filled was followed by one more, which gave
* the active partition's row again, and the walk read that
* partition's pages twice.
*/
public function batchesReachEveryPartitionTestCase()
{
IndexManager::clearCache();
$bundle_path = self::TEST_DIR . "/IndexData200000002";
$index_archive = new IndexDocumentBundle($bundle_path, false,
"TestBundle", self::BATCH_PAGES_PER_PARTITION, 25);
$num_pages = self::BATCH_PAGES_PER_PARTITION *
self::BATCH_PARTITIONS;
$rare_pages = [0, $num_pages - 2];
$docs = [];
for ($i = 0; $i < $num_pages; $i++) {
$description = ($i % 2 == 1) ? "flim" :
(in_array($i, $rare_pages) ? "zorp quib" : "zorp");
$docs[] = [
CC::DOC_ID => $this->docidFromIntKeys($i, $i, $i),
CC::SUMMARY => [
CC::DESCRIPTION => $description,
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => "Page$i",
CC::URL => "https://www.somewhere$i.com/"],
CC::PAGE => "Page $i"];
}
$index_archive->addPages($docs, count($docs));
$index_archive->updateDictionary();
$index_archive->forceSave();
$walk = new WordIterator(L\canonicalTerm("zorp"), $bundle_path,
true, null, 10);
$walk->generation_batch_size = self::BATCH_ROWS;
$walk->loadGenerationBatch(0);
$walk->reset();
$this->assertTrue($walk->batch_full,
"zorp has more partitions than one batch of rows");
$walked = 0;
while (is_array($block = $walk->currentDocsWithWord()) &&
$walked <= $num_pages) {
$walked += count($block);
$walk->advance();
}
$this->assertEqual($walked, $num_pages / 2,
"a walk of zorp reaches every page it is on");
$iterators = [];
foreach (["zorp", "quib"] as $word) {
$iterator = new WordIterator(L\canonicalTerm($word),
$bundle_path, true, null, 10);
$iterator->generation_batch_size = self::BATCH_ROWS;
$iterator->loadGenerationBatch(0);
$iterator->reset();
$iterators[] = $iterator;
}
$join = new IntersectIterator($iterators, [0, 1]);
$found = 0;
while (is_array($block = $join->currentDocsWithWord()) &&
$found <= count($rare_pages)) {
$found += count($block);
$join->advance();
}
$this->assertEqual($found, count($rare_pages),
"the join of zorp and quib finds both pages");
}
/**
* walkReadsEveryPostingOnceTestCase walks a word the way UnionIterator
* does, calling findDocsWithWord and then advance, in blocks of one and
* of ten, from first page to last and from last to first. Forty pages
* go into one partition, and the made-up word zeep is on twenty-five of
* them. Each walk must read the twenty-five postings once each.
* advanceSeenDocs counted the postings left from where the read had
* already moved to, so an ascending walk in blocks of one skipped a
* partition's last posting, and one in blocks of ten read some
* postings twice. A descending block could start before the list.
*/
public function walkReadsEveryPostingOnceTestCase()
{
IndexManager::clearCache();
$bundle_path = self::TEST_DIR . "/IndexData200000003";
$index_archive = new IndexDocumentBundle($bundle_path, false,
"TestBundle", 100, 101);
$docs = [];
$zeep_pages = 0;
for ($i = 0; $i < 40; $i++) {
$has_word = ($i % 8 != 3 && $i % 8 != 6 && $i % 8 != 7);
$zeep_pages += $has_word ? 1 : 0;
$docs[] = [
CC::DOC_ID => $this->docidFromIntKeys($i, $i, $i),
CC::SUMMARY => [
CC::DESCRIPTION => $has_word ? "zeep flim" : "flim",
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => "Page$i",
CC::URL => "https://www.somewhere$i.com/"],
CC::PAGE => "Page $i"];
}
$index_archive->addPages($docs, count($docs));
$index_archive->updateDictionary();
$index_archive->forceSave();
foreach ([[1, WordIterator::ASCENDING], [10, WordIterator::ASCENDING],
[1, WordIterator::DESCENDING], [10, WordIterator::DESCENDING]]
as [$block_size, $direction]) {
$walk = new WordIterator(L\canonicalTerm("zeep"), $bundle_path,
true, null, $block_size, $direction);
$read = [];
while (is_array($block = $walk->findDocsWithWord()) &&
count($read) <= 2 * $zeep_pages) {
foreach (array_keys($block) as $doc_key) {
$read[] = $doc_key;
}
$walk->advance();
}
$this->assertEqual(count($read), $zeep_pages, "a walk in " .
"blocks of $block_size, direction $direction, reads " .
"$zeep_pages postings");
$this->assertEqual(count(array_unique($read)), $zeep_pages,
"a walk in blocks of $block_size, direction $direction, " .
"reads each page once");
}
}
/**
* newestCopyIsScoredTestCase checks that the results show the newest
* copy of a page, found in a partition already merged into the
* dictionary. Ten text pages go into partitions of four. Page 6 is a
* newer copy of page 0's address without the word zorp, and page 5 a
* newer copy of page 1's address with it. The results of a
* GroupIterator over a walk of zorp must leave out page 0's address
* and show page 1's address as page 5 alone. The newest copy is
* looked for by GroupIterator::newestCopy, for result pages only.
*/
public function newestCopyIsScoredTestCase()
{
IndexManager::clearCache();
$bundle_path = self::TEST_DIR . "/IndexData200000004";
$index_archive = new IndexDocumentBundle($bundle_path, false,
"TestBundle", 4, 5);
$addresses = [0, 1, 2, 3, 4, 1, 0, 7, 8, 9];
$descriptions = ["zorp", "zorp", "flim", "flim", "flim", "zorp",
"flim", "flim", "flim", "flim"];
$docs = [];
$doc_ids = [];
foreach ($addresses as $i => $address) {
$url = "https://www.somewhere$address.com/";
/* chr(56) marks a text page, the kind whose newest copy is
looked for */
$doc_ids[$i] = L\crawlHash($url, true) .
str_pad("$i", 8, "0", STR_PAD_LEFT) . chr(56) .
str_pad("$address", 7, "0", STR_PAD_LEFT);
$docs[] = [
CC::DOC_ID => $doc_ids[$i],
CC::SUMMARY => [
CC::DESCRIPTION => $descriptions[$i],
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => "Page$i",
CC::URL => $url],
CC::PAGE => "Page $i"];
}
$index_archive->addPages($docs, count($docs));
$index_archive->updateDictionary();
$index_archive->forceSave();
$results = new GroupIterator(new WordIterator(
L\canonicalTerm("zorp"), $bundle_path, true, null, 10));
$results->latest_copy_fraction = 1;
$keys = [];
$block = $results->nextDocsWithWord();
foreach (is_array($block) ? $block : [] as $page) {
foreach ($page[CC::SUMMARY_OFFSET] ?? [] as $offset) {
if (count($offset) > 2) {
$keys[] = $offset[1];
}
}
}
$this->assertFalse(in_array($doc_ids[0], $keys),
"page 0 is left out, as its newest copy lacks zorp");
$this->assertFalse(in_array($doc_ids[1], $keys),
"page 1 is not shown as it was");
$this->assertEqual($keys, [$doc_ids[5]],
"page 1's address is shown once, as page 5");
}
/**
* docidFromIntKeys makes the document id of a test page from three
* small numbers, padding each to the length a real hash has, so a case
* can give each page an id of its own.
* @param int $i_hash_url an integer that is supposed to be used
* to correspond to the hash of a url component of a doc_id
* @param int $j_hash_page an integer that is supposed to be used
* to correspond to the hash of a web page component of a doc_id
* @param int $k_hash_host an integer that is supposed to be used
* to correspond to the hash of a url's host component of a doc_id
* @param bool $is_doc whether to make a doc_id for a link to doc item or
* for a document
* @return string doc_id to associate with that integer
*/
protected function docidFromIntKeys($i_hash_url, $j_hash_page,
$k_hash_host, $is_doc = true)
{
$doc_or_link = ($is_doc) ? "d" : "l";
return str_pad("$i_hash_url", 8, "0", STR_PAD_LEFT) .
str_pad("$j_hash_page", 8, "0", STR_PAD_LEFT) .
$doc_or_link .
str_pad("$k_hash_host", 7, "0", STR_PAD_LEFT);
}
/**
* positionsReadCapTestCase checks that a positions read whose length
* is past the maximum readable posting
* length is treated as corrupt and skipped, reading nothing, while a
* length within bounds reads and decodes the positions normally. This
* guards the positions read the way the posting-string read is guarded,
* so a corrupt length cannot make the server allocate a huge block.
*/
public function positionsReadCapTestCase()
{
$positions = [3, 7, 11];
$encoded = L\encodePositionList($positions);
$positions_file = C\TEST_DIR . "/test_files/positions_cap_test.bin";
file_put_contents($positions_file, $encoded);
$handle = fopen($positions_file, "r");
$iterator = (new \ReflectionClass(WordIterator::class))->
newInstanceWithoutConstructor();
$within = $iterator->getPositionsList(["POSITIONS_LEN" =>
strlen($encoded), "POSITIONS_OFFSET" => 0,
"FREQUENCY" => count($positions)], strlen($encoded) + 1000,
$handle);
$this->assertEqual($positions, $within,
"a positions length within bounds reads and decodes");
$before = memory_get_usage();
$skipped = $iterator->getPositionsList(["POSITIONS_LEN" =>
C\MAX_POSTING_READ_LEN + 1, "POSITIONS_OFFSET" => 0,
"FREQUENCY" => 1], C\MAX_POSTING_READ_LEN * 4, $handle);
$after = memory_get_usage();
$this->assertEqual([], $skipped,
"a positions length past the cap is skipped");
$this->assertTrue($after - $before < C\MAX_POSTING_READ_LEN,
"the skipped read allocates nothing large");
fclose($handle);
unlink($positions_file);
}
/**
* divergenceScoreTestCase checks the field-weighted divergence score:
* with no occurrences it is log2(1 + o), where o is the expected
* occurrences of the term per document, it rises as the weighted
* frequency rises, and it never reaches log2(1 + 1/o), so a host match
* on top of a title match still adds to the score.
*/
public function divergenceScoreTestCase()
{
$occurrences_per_doc = 0.0607;
$this->assertEqual(round(WordIterator::divergenceScore(
$occurrences_per_doc, 0), 6), round(log(1 + $occurrences_per_doc,
2), 6), "no occurrences give log2(1 + o)");
$body = WordIterator::divergenceScore($occurrences_per_doc, 0.3);
$title = WordIterator::divergenceScore($occurrences_per_doc, 5 + 0.3);
$host_and_title = WordIterator::divergenceScore($occurrences_per_doc,
6 + 5 + 0.3);
$this->assertTrue($body < $title && $title < $host_and_title,
"more weighted occurrences score higher");
$this->assertTrue($host_and_title <
log(1 + 1 / $occurrences_per_doc, 2),
"the score stays below log2(1 + 1/o)");
}
/**
* fieldKeyScoredFromOtherKeyTestCase checks that a union in which a
* word's field key part is paired with the word's other key part
* scores the same pages as a union that walks the field key itself,
* while reading fewer postings. Twenty-four English pages go into
* partitions of four. The made-up word zorp is on every page, and in
* the title of the even ones, so those are filed under zorp's field
* key. The made-up word quib is on five pages spread over the
* partitions. The block holds five pages, so quib's five fill it, and
* the field key part then only adds relevance to them. Both unions are
* read for two blocks, the second showing the field key part was left
* where its own walk would have left it.
*/
public function fieldKeyScoredFromOtherKeyTestCase()
{
IndexManager::clearCache();
$bundle_path = self::TEST_DIR . "/IndexData200000003";
$index_archive = new IndexDocumentBundle($bundle_path, false,
"TestBundle", 4, 5);
$quib_pages = [1, 6, 11, 16, 21];
$docs = [];
for ($i = 0; $i < 24; $i++) {
$docs[] = [
CC::DOC_ID => $this->docidFromIntKeys($i, $i, $i),
CC::SUMMARY => [
CC::DESCRIPTION => in_array($i, $quib_pages) ?
"zorp flim quib" : "zorp flim",
CC::HASH => str_pad("$i", 8, "0", STR_PAD_LEFT),
CC::TITLE => ($i % 2 == 0) ? "Zorp$i zorp" : "Page$i",
CC::URL => "https://www.somewhere$i.com/",
CC::LANG => "en-US"],
CC::PAGE => "Page $i"];
}
$index_archive->addPages($docs, count($docs));
$index_archive->updateDictionary();
$index_archive->forceSave();
$keys = [L\combinedTerm("quib", "en", "all"),
L\combinedTerm("zorp", "en", "all" .
IndexDocumentBundle::FIELD_TERM_MARK),
L\combinedTerm("zorp", "en", "all")];
$blocks = [];
$reads = [];
foreach ([[], [1 => 2]] as $walk => $field_parts) {
$iterators = [];
foreach ($keys as $key) {
$iterators[] = new WordIterator($key, $bundle_path, true,
null, 10);
}
$union = new UnionIterator($iterators, $bundle_path, [],
$field_parts);
$union->results_per_block = count($quib_pages);
L\AnalyticsManager::set(L\AnalyticsManager::TIMINGS, []);
for ($block = 0; $block < 2; $block++) {
$found = $union->currentDocsWithWord();
$blocks[$walk][$block] = [];
foreach (is_array($found) ? $found : [] as $key => $page) {
$blocks[$walk][$block][bin2hex($key)] =
round($page[CC::RELEVANCE], 9);
}
ksort($blocks[$walk][$block]);
$union->advance();
}
$reads[$walk] = L\AnalyticsManager::get(
L\AnalyticsManager::TIMINGS)["postings reads"][0] ?? 0;
}
$this->assertEqual(count($blocks[0][0]), count($quib_pages),
"the first block holds the quib pages");
$this->assertTrue(count($blocks[0][1]) > 0,
"the second block holds pages");
$this->assertEqual($blocks[1], $blocks[0],
"both unions give the same pages with the same relevance");
$iterators = [];
foreach ([$keys[0], $keys[2]] as $key) {
$iterators[] = new WordIterator($key, $bundle_path, true,
null, 10);
}
$union = new UnionIterator($iterators, $bundle_path);
$union->results_per_block = count($quib_pages);
$found = $union->currentDocsWithWord();
$without_field = [];
foreach (is_array($found) ? $found : [] as $key => $page) {
$without_field[bin2hex($key)] = round($page[CC::RELEVANCE], 9);
}
ksort($without_field);
$this->assertTrue($without_field != $blocks[0][0],
"the field key adds relevance to the quib pages it holds");
$this->assertTrue($reads[1] < $reads[0],
"the paired union reads fewer postings");
}
}
- Yioop Repo - Seekquarry