<?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\configs as C;
use seekquarry\yioop\controllers\SearchController;
use seekquarry\yioop\library as L;
use seekquarry\yioop\library\CrawlConstants;
use seekquarry\yioop\library\IndexManager;
use seekquarry\yioop\library\SyntheticWeb;
use seekquarry\yioop\library\language_processing\PhraseParser;
use seekquarry\yioop\models as M;
/*
* This script checks the index a synthetic crawl left behind, by asking
* it questions through the search API and comparing the answers with
* the pages the synthetic web would have served. A synthetic page is
* worked out from its number and the crawl's seed alone, so every page
* the index holds can be built again here and the index's word for it
* checked against the page itself. Run it from the command line once a
* crawl has been stopped:
*
* php SyntheticIndexExperiment.php <crawl timestamp> [pages]
*
* from the tests folder, where the crawl timestamp is the number that
* names the crawl in Manage Crawls and pages is how many pages to sample
* from the index, twenty if left out. It prints what each check asks
* and the numbers it measured, then a summary. It changes nothing in
* the index or the work directory.
*/
if (php_sapi_name() != 'cli' ||
defined("seekquarry\\yioop\\configs\\IS_OWN_WEB_SERVER")) {
echo "BAD REQUEST";
exit();
}
/**
* Calculate base directory of script
* @ignore
*/
define("seekquarry\\yioop\\configs\\PARENT_DIR", substr(
dirname(realpath($_SERVER['PHP_SELF'])), 0, -strlen("/tests")));
define("seekquarry\\yioop\\configs\\BASE_DIR", C\PARENT_DIR . "/src");
require_once C\BASE_DIR . '/configs/Config.php';
/**
* How many failures of a check are listed under it. A check that fails
* for every page would otherwise print a line for each.
*/
const FAILURES_TO_LIST = 5;
/**
* LOCAL_ONLY holds the two control words added to every query the
* experiment asks. Without no:network, SearchController sends a query
* over the network to each queue server MachineModel lists, unless the
* only one is the name server on this host or the index has a
* no_network.txt file; such a query answers only if every server's web
* app answers in time, which tests the network, not the index. Without
* no:cache, PhraseModel may give back an answer kept in the query file
* cache when the site's file cache is on. With both, every query reads
* this machine's copy of the index as it is now.
*/
const LOCAL_ONLY = "no:network no:cache";
/**
* WALK_HELD_PAGES is how many pages the random walk finds in the index
* to be checked beside the site:all sample. site:all gives the first
* pages crawled; the walk gives pages from deeper in the web.
*/
const WALK_HELD_PAGES = 10;
/**
* Most steps a walk of the made-up web takes before it stops, whatever
* the stopping rule says, so a walk cannot run forever
*/
const WALK_STEPS_MOST = 40;
/**
* Most walks made for each held page asked for. A walk often stops on a
* page the crawl did not fetch, so this bounds how long the sampler
* keeps walking when few of the pages it reaches are in the index.
*/
const WALKS_PER_HELD_PAGE_MOST = 100;
/**
* A query taking at least this many seconds is printed as it happens,
* so a run over a large index names the questions that are slow rather
* than every question it asks
*/
const SLOW_QUERY_SECONDS = 5;
/**
* The run prints something at least this often, in seconds, so a long
* step is seen to be moving
*/
const HEARTBEAT_SECONDS = 5;
/**
* How many results to ask for when a page has to be found among the
* results for a query. A page's rarest term has a short posting list,
* so the page sits within this many results if it was indexed at all.
*/
const RESULTS_TO_SCAN = 200;
/**
* RARE_WORDS_JOINED is how many of a page's least common words check 2
* searches for together. Each is on a small share of pages, so the pages
* holding all of them are few however large the crawl, and the page
* itself falls within the results read.
*/
const RARE_WORDS_JOINED = 5;
/**
* heldUrlsFromWalks draws pages the index holds by walking the made-up
* web. A walk starts at the seed page and steps to one of the pages that
* page links to. After t steps a walk can have reached d^t of the s
* pages of the crawl, so it stops with probability d^t/s, which sends it
* deeper the larger the crawl is. The page it stops on is looked up at
* once with info:, and kept if the index holds it and it was not kept
* before. The walk runs again until as many held pages as were asked
* for are found, or WALKS_PER_HELD_PAGE_MOST walks for each have been
* made. The experiment calls it after site:all, so its checks also
* cover pages from deeper in the web than the first ones crawled.
*
* @param object $controller the SearchController the lookups go through
* @param int $timestamp the timestamp of the crawl's index
*
* @param array $settings the crawl's settings, which say the shape of
* the web, the seed it was made from and how many pages each page
* links to
* @param int $how_many how many held pages to find
* @param int $pages_in_crawl how many pages the crawl visited, which is
* the s of the stopping rule
* @return array the urls of the held pages found, each a string
*/
function heldUrlsFromWalks($controller, $timestamp, $settings, $how_many,
$pages_in_crawl)
{
$urls = [];
$seen = [];
$seed_url = SyntheticWeb::seedUrl($settings['graph_type'],
$settings['out_degree'],
$settings['domain_link_probability'] ?? 0);
$degree = max(2, intval($settings['out_degree']));
$size = max($degree, intval($pages_in_crawl));
$walk_start = microtime(true);
$walks = 0;
while (count($urls) < $how_many) {
$url = $seed_url;
$step = 0;
while (true) {
/* A walk of t steps can have reached d^t of the s pages, so
d^t/s is the share of the web it could be standing on by
then. Stopping with that probability puts the walk deeper
in the graph the larger the web is, and stops it once the
steps taken could have covered the web. */
$reach = pow($degree, $step) / $size;
if ($step > 0 && (SyntheticWeb::hashProbability(
$settings['seed'] . ":walk:$walks:$step") < $reach ||
$step >= WALK_STEPS_MOST)) {
break;
}
$tuple = SyntheticWeb::pageTuple($url, $settings['graph_type']);
if (empty($tuple)) {
break;
}
$anchors = pageAnchors($tuple, $settings, implode(".", $tuple));
$pages_linked = [];
foreach ($anchors as $anchor) {
if (empty($anchor['is_image'])) {
$pages_linked[] = $anchor['url'];
}
}
if (empty($pages_linked)) {
break;
}
$which = intval(SyntheticWeb::hashProbability(
$settings['seed'] . ":step:$walks:$step") *
count($pages_linked));
$url = $pages_linked[min($which, count($pages_linked) - 1)];
$step++;
}
$walks++;
if (!isset($seen[$url])) {
$seen[$url] = true;
if (askIndex($controller, $timestamp, "info:$url",
"walk lookup") >= 1) {
$urls[] = $url;
}
}
heartbeat(sprintf(" %d of %d held pages found in %d walk(s), " .
"%.0f seconds so far", count($urls), $how_many, $walks,
microtime(true) - $walk_start));
if ($walks >= $how_many * WALKS_PER_HELD_PAGE_MOST) {
printf(" the walk found only %d of the %d held pages asked " .
"for in %d walks\n", count($urls), $how_many, $walks);
break;
}
}
printf(" %d held pages found from %d walk(s) in %.1f seconds\n",
count($urls), $walks, microtime(true) - $walk_start);
return $urls;
}
/**
* sampleUrlsFromIndex asks the index for the pages it holds, with the
* query site:all, and gives back up to $how_many of their urls, keeping
* only page urls, which end in /index.html, and leaving out images and
* robots files. The experiment's checks are then made over pages the
* crawl fetched, as many as were asked for or all the index holds.
*
* @param object $controller the SearchController queries are asked through
* @param int $timestamp the timestamp of the crawl's index
* @param int $how_many how many urls to give back at most
* @return array the urls, each a string
*/
function sampleUrlsFromIndex($controller, $timestamp, $how_many)
{
$data = $controller->queryRequest("site:all i:$timestamp " . LOCAL_ONLY,
$how_many,
0, 1);
$urls = [];
foreach ($data['PAGES'] ?? [] as $result) {
$url = trim($result[CrawlConstants::URL] ?? "");
if (preg_match('/\/index\.html$/', $url) &&
!in_array($url, $urls)) {
$urls[] = $url;
}
}
return $urls;
}
/**
* describeRecord lists the fields of one record the query engine gave
* back, one to a line, each under the name CrawlConstants gives its key,
* so a reader sees what the index stored for a page. Long values are cut
* to their first RECORD_VALUE_SHOWN characters. Check 1 calls it for the
* first page whose stored title is wrong.
*
* @param array $record the record, keyed by CrawlConstants letters
* @return string the lines, each ending in a newline
*/
function describeRecord($record)
{
$names = array_flip((new \ReflectionClass(CrawlConstants::class))->
getConstants());
$lines = "";
foreach ($record as $key => $value) {
$shown = is_scalar($value) ? (string)$value : json_encode($value);
$lines .= sprintf(" %s: %s\n", $names[$key] ?? $key,
mb_substr($shown, 0, RECORD_VALUE_SHOWN));
}
return ($lines === "") ? " (the record is empty)\n" : $lines;
}
/**
* RECORD_VALUE_SHOWN is how many characters of each field describeRecord
* shows, enough to see what a field holds without printing a whole page.
*/
const RECORD_VALUE_SHOWN = 100;
/**
* RANK_CHECK is the summary line of check 5, which asks about words rather
* than held pages and so is still made when no page is held.
*/
const RANK_CHECK = "check 5: rarer words are on fewer pages, and every " .
"word is on some page";
/**
* How many sampled pages the conjunctive check asks about. It is a
* check of the query engine rather than of the index, so a few pages
* are enough to say whether an intersection answers as its parts do.
*/
const CONJUNCTIVE_PAGES = 10;
/**
* The term ranks whose document counts are read to see the shape of the
* term distribution. A power law shows as counts that fall as the rank
* doubles, so ranks are taken at doublings.
*/
const ZIPF_RANKS = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
/**
* How many pages to sample when no count is given on the command line.
*/
const DEFAULT_SAMPLE = 20;
/**
* How many links of each sampled page are asked about. A page carries
* ten, and one of them asked for every page of the sample says as much
* about the link records as three of them do, for a third of the work.
*/
const LINKS_PER_PAGE = 1;
/**
* How many sampled pages are asked about the image they link to. A
* crawl stopped early has not fetched every image it saw, so this is a
* report rather than a check, and a few pages say as much as all of
* them.
*/
const IMAGE_PAGES = 10;
$timestamp = intval($argv[1] ?? 0);
$sample_size = intval($argv[2] ?? DEFAULT_SAMPLE);
if ($timestamp <= 0) {
$script = basename($argv[0]);
echo "Usage: php $script <crawl timestamp> [pages to sample]\n" .
" crawl timestamp: the number that names the crawl in Manage " .
"Crawls,\n such as 1789346511\n" .
" pages to sample: how many pages to draw from the index and " .
"check,\n " . DEFAULT_SAMPLE . " if left out\n";
exit();
}
if (!C\p('API_ACCESS')) {
echo "The search API is off. Turn on API Access under Server " .
"Settings and run this again.\n";
exit();
}
$checks = [];
/* A run reads the site's own settings, and a site with error display
off ends a run on a fatal error without a word, which is how a run
that met a url it could not read looked like a run that stopped for
no reason. This says what ended it, on the way out. */
register_shutdown_function(function () {
$error = error_get_last();
if (!empty($error) && in_array($error['type'],
[E_ERROR, E_PARSE, E_CORE_ERROR, E_COMPILE_ERROR, E_USER_ERROR])) {
echo "\nThe run ended on an error: " . $error['message'] .
" in " . $error['file'] . " line " . $error['line'] . "\n";
}
});
$controller = new SearchController();
$crawl_model = new M\CrawlModel();
$settings = SyntheticWeb::settingsFromSeedInfo(
$crawl_model->getCrawlSeedInfo($timestamp));
if ($settings == []) {
echo "Crawl $timestamp is not a synthetic crawl, or its seed " .
"information could not be read.\n";
exit();
}
echo "Preliminary work\n";
echo "----------------\n";
echo "1. Getting crawl settings, which is what a page of this crawl is " .
"rebuilt from.\n";
$info = $crawl_model->getInfoTimestamp($timestamp);
$stored = intval($info['COUNT'] ?? 0);
$visited = intval($info['VISITED_URLS_COUNT'] ?? 0);
printf(" crawl %d: graph %s, out degree %d, seed %d, term exponent " .
"%s,\n document length %d, pages visited %d, records stored %d\n",
$timestamp, $settings['graph_type'], $settings['out_degree'],
$settings['seed'], $settings['term_exponent'],
$settings['doc_length'], $visited, $stored);
echo "\n2. Sampling urls: the query site:all asks the index for its " .
"first $sample_size\n pages, which gives as many pages as asked " .
"for or all the index holds,\n whichever is fewer. Only page urls " .
"are kept, not images or robots files.\n";
$queue_servers = $controller->model("machine")->getQueueServerUrls();
$over_network = !empty($queue_servers) &&
!$controller->model("phrase")->isSingleLocalhost($queue_servers,
$timestamp);
echo " Queue servers listed: " . count($queue_servers) . ". Without " .
"no:network a query\n would " . ($over_network ? "" : "not ") .
"be sent over the network. Every query here carries " . LOCAL_ONLY .
",\n so it reads the index on this machine and no cached answer.\n";
$sample = sampleUrlsFromIndex($controller, $timestamp, $sample_size);
echo " " . count($sample) . " urls from site:all.\n";
echo " A random walk then starts at the seed page and steps to one of " .
"the pages\n that page links to. After t steps a walk can have " .
"reached d^t of the s\n pages of the crawl, so it stops with " .
"probability d^t/s. The page it stops\n on is looked up at once " .
"with info:, and kept if the index holds it; the\n walk runs " .
"again until " . WALK_HELD_PAGES . " held pages are found.\n";
$walked = heldUrlsFromWalks($controller, $timestamp, $settings,
WALK_HELD_PAGES, $visited);
echo " " . count($walked) . " held urls from the walk.\n";
$sample = array_values(array_unique(array_merge($sample, $walked)));
$sample_size = count($sample);
$titles_right = 0;
$found_by_rare_term = 0;
$rare_query_shown = "";
$joined_pairs = [];
$link_query_shown = "";
$one_record_each = 0;
$no_record = 0;
$several_records = 0;
$links_seen = 0;
$link_misses = [];
$title_misses = [];
$rare_term_misses = [];
$record_misses = [];
$rank_misses = [];
$linker_misses = [];
$conjunctive_misses = [];
$links_tried = 0;
$images_found = 0;
$images_tried = 0;
$skipped = 0;
$index_bundle = IndexManager::getIndex($timestamp);
$partitions_written = intval($index_bundle->documents->parameters[
"SAVE_PARTITION"] ?? 0) + 1;
$partitions_searchable = intval($index_bundle->next_partition_to_add ?? 0);
echo "\n3. Checking how much of the crawl the dictionary holds. A query sees " .
"only the\n partitions the dictionary updater has added, and the " .
"partition being written.\n";
printf(" %d of the %d partitions the crawl wrote are in the dictionary\n",
$partitions_searchable, $partitions_written);
if ($partitions_searchable + 1 < $partitions_written) {
echo " the rest cannot be found by any query, so a check below can " .
"fail for a page\n the crawl fetched but the dictionary has not " .
"yet taken in\n";
}
echo "\n4. Confirming the index holds each sampled url, both from its " .
"info: row in the\n dictionary and through the query engine. The " .
"sample came from the index, so\n every url should be held.\n";
$held_urls = [];
$records_of = [];
$in_dictionary = 0;
/* The count for the commonest word is asked here, before the page
checks, and again in check 5 after them. If it is in the millions
here and 0 there, the page checks themselves leave the query engine
unable to answer; if it is 0 both times, the query engine cannot
answer this index at all on this run. */
$rank_one_before = askIndex($controller, $timestamp, sprintf("%08d", 1),
"one common word");
foreach ($sample as $url) {
$records = askIndex($controller, $timestamp, "info:$url", "page url");
$records_of[$url] = $records;
if ($records >= 1) {
$held_urls[] = $url;
}
if (dictionaryDocuments($timestamp, "info:$url") > 0) {
$in_dictionary++;
}
}
printf(" %d of %d sampled urls have an info: row in the dictionary, " .
"read without\n the query engine\n", $in_dictionary, count($sample));
printf(" %d of %d sampled urls are in the index\n", count($held_urls),
count($sample));
$sample = $held_urls;
if (empty($sample)) {
echo " none of the sampled urls is in the index, so no check " .
"below can be made\n";
}
echo "\nPerforming the following checks\n";
echo "-------------------------------------------\n";
echo "Checks 1 to 4 ask the index about each held page in turn. A " .
"line below\nsays how far the run has got, at most one every " .
HEARTBEAT_SECONDS . " seconds, and a query\nof its own that takes " .
SLOW_QUERY_SECONDS . " seconds or more is named where it happens.\n";
$run_start = microtime(true);
/* Checks 6 and 7 come after the page checks, and on some runs they
fail on pages where the run before passed them with the same queries.
Their queries are asked here as well, before the page checks. If they
answer here and not later in the same run, something the run does in
between stops them answering; if they fail here too, the order of the
queries in a run is not the cause. */
$early_linkers = 0;
$early_joins = 0;
$early_pages = array_slice($sample, 0, CONJUNCTIVE_PAGES);
foreach ($early_pages as $url) {
$tuple = SyntheticWeb::pageTuple($url, $settings['graph_type']);
foreach (pageAnchors($tuple, $settings, implode(".", $tuple)) as
$anchor) {
if (!$anchor['is_image']) {
if (askIndex($controller, $timestamp, "link:" . $anchor['url'],
"early linkers") >= 1) {
$early_linkers++;
}
break;
}
}
$terms = SyntheticWeb::terms(implode(".", $tuple), $settings['seed'],
$settings['term_exponent'], $settings['doc_length'],
$settings['length_spread']);
if (urlAmongResults($controller, $timestamp, max($terms) .
" info:$url", $url, "early join", 1)) {
$early_joins++;
}
}
$pages_done = 0;
$title_record_shown = "";
foreach ($sample as $url) {
$tuple = SyntheticWeb::pageTuple($url, $settings['graph_type']);
$page_key = implode(".", $tuple);
$held = $controller->queryRequest("info:$url i:$timestamp " .
LOCAL_ONLY, 1, 0, 1);
$stored_title = trim($held['PAGES'][0][CrawlConstants::TITLE] ?? "");
if ($stored_title == "page $page_key") {
$titles_right++;
} else if (count($title_misses) < FAILURES_TO_LIST) {
$title_misses[] = "$url: index says \"$stored_title\", the page " .
"is \"page $page_key\"";
if ($title_record_shown === "") {
$title_record_shown = describeRecord($held['PAGES'][0] ?? []);
}
}
$terms = SyntheticWeb::terms($page_key, $settings['seed'],
$settings['term_exponent'], $settings['doc_length'],
$settings['length_spread']);
$distinct_terms = array_unique($terms);
rsort($distinct_terms);
/* Without no:rewrite, PhraseModel::rewriteAsDisjunctiveQuery turns
words separated by spaces into a search for any one of them, since
USE_CONJUNCTIVE_QUERY is false by default. The check wants pages
holding all five, so it asks with no:rewrite. */
/* PhraseParser::hyphenateEntities joins two neighboring query words
into one term when the n-gram Bloom filter says they are a known
phrase, and the filter answers yes for some pairs of these made-up
words. The joined term is on no page, so such a query finds
nothing. A word that the parser would join to the one before it is
left out, the pair is reported, and the next least common word is
tried instead. */
$rare_words = [];
foreach ($distinct_terms as $word) {
if (count($rare_words) >= RARE_WORDS_JOINED) {
break;
}
$trial = array_merge($rare_words, [$word]);
$parsed = array_filter(PhraseParser::extractPhrases(
implode(" ", $trial), "en-US"));
if (count($parsed) == count($trial)) {
$rare_words = $trial;
} else if (count($joined_pairs) < FAILURES_TO_LIST) {
$joined_pairs[] = end($rare_words) . " $word";
}
}
$rare_query = implode(" ", $rare_words) . " no:rewrite";
if ($rare_query_shown === "") {
$rare_query_shown = $rare_query;
}
if (urlAmongResults($controller, $timestamp, $rare_query, $url,
"least common words")) {
$found_by_rare_term++;
} else if (count($rare_term_misses) < FAILURES_TO_LIST) {
/* Each word is asked for alone with the page's url, and the page
must be among the answers; the count a query reports is an
estimate and can be above zero when nothing is found. */
$not_held = [];
foreach (array_slice($distinct_terms, 0, RARE_WORDS_JOINED) as
$word) {
if (!urlAmongResults($controller, $timestamp, "$word info:$url",
$url, "least common words", 1)) {
$not_held[] = $word;
}
}
$rare_term_misses[] = "$url: not in the results for $rare_query; " .
(empty($not_held) ? "each word alone with info: finds the page" :
"not held for it: " . implode(" ", $not_held));
}
$records = $records_of[$url];
if ($records == 1) {
$one_record_each++;
} else if ($records == 0) {
$no_record++;
} else {
$several_records++;
if (count($record_misses) < FAILURES_TO_LIST) {
$record_misses[] = "$url: $records records under this url";
}
}
$anchors = pageAnchors($tuple, $settings, $page_key);
$page_links = 0;
$image_url = "";
foreach ($anchors as $anchor) {
if ($anchor['is_image']) {
if ($image_url === "") {
$image_url = $anchor['url'];
}
continue;
}
if ($page_links >= LINKS_PER_PAGE) {
continue;
}
$page_links++;
$links_tried++;
$link_query = "link:" . $anchor['url'] . " info:$url";
if ($link_query_shown === "") {
$link_query_shown = $link_query;
}
/* A join reports as its count the least of its words' counts, so
the count is above zero whether or not a page holds both; the
page itself has to be among the answers. */
if (urlAmongResults($controller, $timestamp, $link_query, $url,
"link", 1)) {
$links_seen++;
} else if (count($link_misses) < FAILURES_TO_LIST) {
$link_misses[] = ["from" => $url, "to" => $anchor['url']];
}
}
if ($image_url !== "" && $images_tried < IMAGE_PAGES) {
$images_tried++;
if (askIndex($controller, $timestamp, "info:$image_url",
"image url") >= 1) {
$images_found++;
}
}
$pages_done++;
heartbeat(sprintf(" still asking about pages: %d of %d done, %.0f " .
"seconds so far, %d bytes held", $pages_done, count($sample),
microtime(true) - $run_start, memory_get_usage()));
}
$count = count($sample) - $skipped;
if ($skipped > 0) {
echo " $skipped sampled url(s) were not pages of the made-up web " .
"and were passed over\n";
}
echo "\nCheck 1: for each held page, the title the index holds " .
"matches the title of\nthe synthetic page.\n";
printf("%d out of %d matched.\n", $titles_right, $count);
listFailures($title_misses, $count - $titles_right);
if ($title_record_shown !== "") {
echo "The first page with a wrong title is stored as follows. An error " .
"code or an\nempty description says the fetch failed and the " .
"failure was stored; the\npage's words with no title say the " .
"title was lost while the page was\nsummarized.\n" .
$title_record_shown;
}
$checks["check 1: each held page has the right title in the index"] =
($titles_right == $count);
echo "\nCheck 2: for each held page, search for its " . RARE_WORDS_JOINED .
" least common words\ntogether, and look for the page in the first " .
RESULTS_TO_SCAN . " results. no:rewrite\nmakes the search ask for " .
"pages holding all of the words; without it Yioop\nasks for pages " .
"holding any of them. For the first held page the query\nwas: " .
"$rare_query_shown\n";
$rare_term_asked = $count;
printf("%d of %d pages were found.\n", $found_by_rare_term,
$rare_term_asked);
if (!empty($joined_pairs)) {
echo "The query parser joins some pairs of these words into one term " .
"(its n-gram\nfilter takes them for a known phrase), so such " .
"pairs were not asked\ntogether. For example: " .
implode(", ", $joined_pairs) . "\n";
}
listFailures($rare_term_misses, $rare_term_asked - $found_by_rare_term);
$checks["check 2: searching for a page's least common words together " .
"finds the page"] =
($rare_term_asked > 0 && $found_by_rare_term == $rare_term_asked);
echo "\nCheck 3: for each held page, the index holds exactly one record " .
"under the\npage's url, not two or more.\n";
printf("%d out of %d passed.\n", $one_record_each, $count);
listFailures($record_misses, $count - $one_record_each);
$checks["check 3: no held page is stored twice"] =
($one_record_each == $count);
echo "\nCheck 4: for each held page, take the first page it links to, " .
"and search for\nlink: that page together with info: the held page. " .
"The held page links to it,\nso the search should find the held " .
"page. For the first held page the query\nwas: $link_query_shown\n";
printf("%d of %d searches found the page.\n", $links_seen, $links_tried);
if (!empty($link_misses)) {
echo "\nA link the index did not answer for is asked about four more " .
"ways below.\nThe row says how many records the index reports " .
"for: the link record of the\ntarget under its url, the same " .
"under the hash of that url, the page that\ncarries the link, " .
"and the target page itself. A link record that answers\nunder " .
"the hash but not under the url says the url form is what is " .
"wrong;\nnone of them answering says the link record is not in " .
"the index at all.\n";
foreach ($link_misses as $miss) {
$counts = [];
foreach (["link:" . $miss["to"],
"link:" . L\crawlHash($miss["to"]),
"info:" . $miss["from"], "info:" . $miss["to"]] as $query) {
$counts[] = askIndex($controller, $timestamp, $query,
"link asked four ways");
}
$link_info = IndexManager::getWordInfo($timestamp,
L\canonicalTerm("link:" . $miss["to"]));
echo " " . $miss["to"] . ": link url " . $counts[0] .
", link hash " . $counts[1] . ", linking page " . $counts[2] .
", target page " . $counts[3] . ", link rows in the " .
"dictionary " . count($link_info["ROWS"] ?? []) . "\n";
}
}
$checks["check 4: searching for link: a target with info: a page " .
"linking to it finds the page"] =
($links_tried > 0 && $links_seen == $links_tried);
echo "Image links whose image is in the index: $images_found of " .
"$images_tried pages asked\n (a report rather than a check: a " .
"crawl stopped early has not fetched every\n image it saw)\n";
$vocabulary = $settings['doc_length'] * 10;
echo "\nCheck 5: the number of documents the index reports for a term " .
"falls as the\nterm's rank rises, and no term of the crawl's " .
"$vocabulary-term vocabulary reports none.\n";
$step_start = microtime(true);
$previous = PHP_INT_MAX;
$falls = true;
$counts_by_rank = [];
foreach (ZIPF_RANKS as $rank) {
if ($rank > $vocabulary) {
continue;
}
$rows = askIndex($controller, $timestamp, sprintf("%08d", $rank),
"one common word");
$counts_by_rank[] = $rows;
printf(" rank %5d: %d documents by query, %d in the dictionary\n",
$rank, $rows, dictionaryDocuments($timestamp, sprintf("%08d", $rank)));
if ($rank == 1) {
printf(" the same query before the page checks: %d\n",
$rank_one_before);
}
/* A query on an index built with combined terms reads the key that
joins the word to the lang: and safe: words the query adds, while
the count above is the word's own key. These are the combined keys
for the language guessed from the word, so a gap between the query
and the dictionary shows whether the key is missing or unread. */
$word = sprintf("%08d", $rank);
$lang = explode("-", L\guessLocaleFromString($word))[0];
$combined = [];
foreach (["true", "all"] as $safe) {
$info = IndexManager::getWordInfo($timestamp,
L\combinedTerm($word, $lang, $safe));
$combined[] = "safe:$safe " . array_sum(array_map('intval',
array_column($info["ROWS"] ?? [], "NUM_DOCS")));
}
echo " combined key with lang:$lang: " . implode(", ", $combined) .
"\n";
if ($rows == 0) {
$rank_misses[] = "rank $rank: no documents";
} else if ($rows > $previous) {
$rank_misses[] = "rank $rank: $rows documents, more than the " .
"$previous of the rank before";
}
if ($rows > $previous || $rows == 0) {
/* A rank inside the vocabulary is on pages of any crawl, so a
count of 0 is a term the index does not answer for. Counts
that are all 0 do fall, which is how an index answering
nothing passed this check. */
$falls = false;
}
$previous = $rows;
}
printf("%d out of %d ranks passed.\n",
count($counts_by_rank) - count($rank_misses), count($counts_by_rank));
listFailures($rank_misses, count($rank_misses));
$checks[RANK_CHECK] = $falls;
printf(" rank counts took %.1f seconds\n", microtime(true) - $step_start);
echo "\nCheck 6: the first page each held page links to has at " .
"least one linker\nrecorded in the index.\n";
$step_start = microtime(true);
$in_link_counts = [];
foreach ($sample as $url) {
$tuple = SyntheticWeb::pageTuple($url, $settings['graph_type']);
$anchors = pageAnchors($tuple, $settings, implode(".", $tuple));
foreach ($anchors as $anchor) {
if ($anchor['is_image']) {
continue;
}
$linkers = askIndex($controller, $timestamp,
"link:" . $anchor['url'], "linkers of a target");
$in_link_counts[] = $linkers;
if ($linkers < 1 && count($linker_misses) < FAILURES_TO_LIST) {
$linker_misses[] = $anchor['url'] . ": no linkers recorded, " .
"though " . $url . " links to it";
}
break;
}
}
$targets_with_linkers = 0;
foreach ($in_link_counts as $linkers) {
if ($linkers >= 1) {
$targets_with_linkers++;
}
}
printf("%d out of %d passed.\n", $targets_with_linkers,
count($in_link_counts));
listFailures($linker_misses,
count($in_link_counts) - $targets_with_linkers);
printf("The same query for the first %d pages, asked before the page " .
"checks: %d of %d\nanswered.\n", count($early_pages), $early_linkers,
count($early_pages));
$checks["check 6: every link target checked has at least one page " .
"listed as linking to it"] =
(count($in_link_counts) > 0 && min($in_link_counts) >= 1);
echo "\nCheck 7: a query joining a page's rarest term and its url " .
"answers, where each\nof those two answered on its own above. This " .
"asks the query engine rather\nthan the index.\n";
$conjunctive_asked = 0;
$conjunctive_answered = 0;
foreach (array_slice($sample, 0, CONJUNCTIVE_PAGES) as $url) {
$tuple = SyntheticWeb::pageTuple($url, $settings['graph_type']);
$terms = SyntheticWeb::terms(implode(".", $tuple), $settings['seed'],
$settings['term_exponent'], $settings['doc_length'],
$settings['length_spread']);
$conjunctive_asked++;
if (urlAmongResults($controller, $timestamp, max($terms) .
" info:$url", $url, "rarest word and url", 1)) {
$conjunctive_answered++;
} else if (count($conjunctive_misses) < FAILURES_TO_LIST) {
$conjunctive_misses[] = "$url: the join with " . max($terms) .
" answered nothing";
}
}
printf("%d out of %d passed.\n", $conjunctive_answered,
$conjunctive_asked);
printf("The same queries, asked before the page checks: %d of %d " .
"answered.\n", $early_joins, count($early_pages));
listFailures($conjunctive_misses,
$conjunctive_asked - $conjunctive_answered);
$checks["check 7: searching for a page's least common word and its " .
"url finds the page"] =
($conjunctive_asked > 0 && $conjunctive_answered == $conjunctive_asked);
echo "\nSeconds spent by kind of question:\n";
foreach (queryTimings() as $kind => $timing) {
printf(" %-22s %5d asked, %6.1f seconds total, %.2f average, " .
"%.2f slowest\n", $kind, $timing["asked"], $timing["seconds"],
$timing["seconds"] / max(1, $timing["asked"]),
$timing["slowest"]);
if ($timing["slowest"] >= SLOW_QUERY_SECONDS) {
echo " slowest was: " . $timing["slowest_query"] . "\n";
}
}
echo "\nSummary:\n";
if (count($sample) < $sample_size) {
echo " Only $count of the $sample_size sampled pages are in the " .
"index, so each check\n below tested $count pages, not " .
"$sample_size.\n";
}
$failed = 0;
foreach ($checks as $name => $passed) {
/* A check made over no pages has shown nothing, so it is not a pass. */
if ($count == 0 && $name != RANK_CHECK) {
$passed = false;
}
echo " " . ($passed ? "PASS" : "FAIL") . " $name\n";
if (!$passed) {
$failed++;
}
}
echo ($failed == 0) ? "All " . count($checks) . " checks passed.\n" :
"$failed of the " . count($checks) . " checks failed.\n";
exit($failed == 0 ? 0 : 1);
/**
* urlAmongResults asks one term and says whether a page's url is among
* the first RESULTS_TO_SCAN results, which is what the first version of
* this experiment asked and what the runs that passed asked. It is
* timed under the kind given, as the count queries are.
*
* @param SearchController $controller the controller to query through
* @param int $timestamp the crawl the query is asked of
* @param string $query the single term to ask, without the crawl
* @param string $url the url of the page looked for
* @param string $kind what the question is for, the name it is timed
* under
* @param int $results_to_scan how many results to ask for and read
* @return bool whether the page's url is among the results listed
*/
function urlAmongResults($controller, $timestamp, $query, $url, $kind,
$results_to_scan = RESULTS_TO_SCAN)
{
$start = microtime(true);
$data = $controller->queryRequest("$query i:$timestamp " . LOCAL_ONLY,
$results_to_scan, 0, 1);
recordQueryTime($kind, $query, microtime(true) - $start);
foreach ($data['PAGES'] ?? [] as $result) {
if (trim($result[CrawlConstants::URL] ?? "") == $url) {
return true;
}
}
return false;
}
/**
* queryTimings hands back the record of how long each kind of question
* has taken: a map from the name a question is timed under to how many
* were asked, how long they took altogether, and the slowest one and
* its query. The two functions that ask the index add to it, and the
* report at the end of a run reads it.
*
* @return array the record, given back by reference so a caller adds to
* it in place
*/
function &queryTimings()
{
static $timings = [];
return $timings;
}
/**
* recordQueryTime adds one query to the record queryTimings keeps, and
* prints the query when it took longer than SLOW_QUERY_SECONDS or when
* a line of progress is due.
*
* @param string $kind what the question is for, the name it is timed
* under
* @param string $query the query that was asked
* @param float $took how many seconds the index took over it
*/
function recordQueryTime($kind, $query, $took)
{
$timings = &queryTimings();
if ($took >= SLOW_QUERY_SECONDS) {
echo sprintf(" a %s query took %.1f seconds: %s\n", $kind, $took,
$query);
flush();
}
if (empty($timings[$kind])) {
$timings[$kind] = ["asked" => 0, "seconds" => 0, "slowest" => 0,
"slowest_query" => ""];
}
$timings[$kind]["asked"]++;
$timings[$kind]["seconds"] += $took;
if ($took > $timings[$kind]["slowest"]) {
$timings[$kind]["slowest"] = $took;
$timings[$kind]["slowest_query"] = $query;
}
}
/**
* dictionaryDocuments reads how many documents the dictionary lists for a
* word, straight from IndexManager::getWordInfo rather than through the
* query engine. The run prints it beside what a query reports, so when
* a query finds nothing the reader can tell whether the dictionary lost the
* word or the query engine lost what the dictionary holds. Check 5 and the
* step that asks which sampled urls are held both call it.
*
* @param int $timestamp the crawl whose dictionary to read
* @param string $word the word, or a meta word such as info: and a url,
* as a query would give it
* @return int the documents the dictionary's rows for the word add up to
*/
function dictionaryDocuments($timestamp, $word)
{
$info = IndexManager::getWordInfo($timestamp, L\canonicalTerm($word));
return array_sum(array_map('intval', array_column($info["ROWS"] ?? [],
"NUM_DOCS")));
}
/**
* listFailures prints the failures a check collected, under the line
* saying how many passed. It prints nothing when a check had none, and
* where a check failed more times than were kept it says how many more
* there were.
*
* @param array $failures the lines kept, each naming one failure
* @param int $how_many_failed how many failed altogether
*/
function listFailures($failures, $how_many_failed)
{
if ($how_many_failed < 1) {
return;
}
echo "Here are the failures:\n";
foreach ($failures as $line) {
echo " $line\n";
}
$more = $how_many_failed - count($failures);
if ($more > 0) {
echo " and $more more\n";
}
}
/**
* heartbeat prints a line of progress when it is asked to, or when
* nothing has been printed for HEARTBEAT_SECONDS, whichever comes
* first. Every query of the run reports through it, so a run over a
* large index never goes quiet for long, and a query that is slow on
* its own is printed at once.
*
* @param string $line what to print if a line is due
* @param bool $always print the line whether or not one is due
*/
function heartbeat($line, $always = false)
{
static $last_printed = 0;
$now = microtime(true);
if ($always || $now - $last_printed >= HEARTBEAT_SECONDS) {
echo $line . "\n";
flush();
$last_printed = $now;
}
}
/**
* askIndex asks the index one query and gives back how many documents
* it reports. It also keeps, for every kind of question the run asks,
* how many of that kind were asked, how long they took altogether and
* which single one took longest, so a slow run says which question is
* the slow one rather than only that it is slow.
*
* @param SearchController $controller the controller to query through
* @param int $timestamp the crawl the query is asked of, which this
* function adds to the query as the i: term
* @param string $query the query to ask, written without that i: term
* @param string $kind what the question is for, used as the name this
* query is timed under; the empty string times it under "other"
* @return int how many documents the index reports for the query
*/
function askIndex($controller, $timestamp, $query, $kind)
{
$kind = ($kind === "") ? "other" : $kind;
$start = microtime(true);
$data = $controller->queryRequest("$query i:$timestamp " . LOCAL_ONLY, 1,
0, 1);
recordQueryTime($kind, $query, microtime(true) - $start);
return intval($data['TOTAL_ROWS'] ?? 0);
}
/**
* pageAnchors gives the urls a page links to, each marked as an image
* or a page, in the order the page carries them. It draws the same
* choices the synthetic web draws when it writes the page's anchors,
* so the urls are exactly the ones the crawler was handed, in the
* domain or path form each was written in.
*
* @param array $tuple the page's coordinates
* @param array $settings the crawl's synthetic settings
* @param string $page_key the page's coordinates joined by dots
* @return array one entry per anchor, each holding the url under 'url'
* and whether it is an image under 'is_image'
*/
function pageAnchors($tuple, $settings, $page_key)
{
$seed = $settings['seed'];
$is_seed_page = (max($tuple) == 0);
$targets = SyntheticWeb::outLinks($tuple, $settings['graph_type'],
$settings['out_degree'], $seed, $settings['power_law_exponent']);
$anchors = [];
$which = 0;
foreach ($targets as $target) {
$to_domain = SyntheticWeb::hashProbability(
"$seed:dom:$page_key:$which") <
$settings['domain_link_probability'];
$is_image = !$is_seed_page && SyntheticWeb::hashProbability(
"$seed:img:$page_key:$which") <
$settings['image_link_probability'];
$anchors[] = ['url' => $is_image ?
SyntheticWeb::imageUrlForTuple($target, $to_domain) :
SyntheticWeb::urlForTuple($target, $to_domain),
'is_image' => $is_image];
$which++;
}
return $anchors;
}
- Yioop Repo - Seekquarry