<?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\library\storage_formats;
use seekquarry\yioop\library as L;

use seekquarry\yioop\configs as C;
use seekquarry\yioop\library\CrawlConstants;
use seekquarry\yioop\library\CrawlDaemon;
use seekquarry\yioop\library\data_structures\PersistentStructure;
/**
 * Load charCopy
 */
require_once __DIR__ . "/../Utility.php";
/**
 * Data structure used to store one generation worth of the word document
 * index (inverted index). This data structure consists of three main
 * components a word entries, word_doc entries, and document entries.
 *
 * Word entries are described in the documentation for the words field.
 * Word-doc entries are described in the documentation for the word_docs field
 * Document entries are described in the documentation for the doc_infos field
 *
 * IndexShards also have two access modes a $read_only_from_disk mode and
 * a loaded in memory mode. Loaded in memory mode is mainly for writing new
 * data to the shard. When in memory, data in the shard can also be in one of
 * two states packed or unpacked. Roughly, when it is in a packed state it is
 * ready to be serialized to disk; when it is an unpacked state it methods
 * for adding data can be used.
 *
 * Serialized on disk, a shard has a header with document statistics followed
 * by the a prefix index into the words component, followed by the word
 * component itself, then the word-docs component, and finally the document
 * component.
 *
 * @author Chris Pollett
 */
class IndexShard extends PersistentStructure implements CrawlConstants
{
    /**
     * Fraction of NUM_DOCS_PER_PARTITION document inserts before data
     * from the words array is flattened to word_postings. (It will
     * also be flattened during periodic index saves)
     */
    const FLATTEN_FREQUENCY = 10000;
    /**
     * Bytes of tmp string allowed during flattenings
     */
     const WORD_POSTING_COPY_LEN = 32000;
    /**
     * Used to keep track of whether a record in document infos is for a
     * document or for a link
     */
    const LINK_FLAG =  0x800000;
    /**
     * Shard block size is 1<< this power
     */
    const SHARD_BLOCK_POWER = 12;
    /**
     * Size in bytes of one block in IndexShard
     */
    const SHARD_BLOCK_SIZE = 4096;
    /**
     * Header Length of an IndexShard (sum of its non-variable length fields)
     */
    const HEADER_LENGTH = 40;
    /**
     * Length of the data portion of a word entry in bytes in the shard
     */
    const WORD_DATA_LEN = 12;
    /**
     * Length of a word entry's key in bytes
     */
    const WORD_KEY_LEN = 20;
    /**
     * Length of a key in a DOC ID.
     */
    const DOC_KEY_LEN = 8;
    /**
     * Length of  DOC ID.
     */
    const DOC_ID_LEN = 24;
    /**
     * Maximum number of auxiliary document keys;
     */
    const MAX_AUX_DOC_KEYS = 200;
    /**
     * Length of one posting ( a doc offset occurrence pair) in a posting list
     */
    const POSTING_LEN = 4;
    /**
     * Represents an empty prefix item
     */
    const BLANK = "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF";
    /**
     * Flag used to indicate that a word item should not be packed or unpacked
     */
    const HALF_BLANK = "\xFF\xFF\xFF\xFF";
    /**
     * Represents an empty prefix item
     */
    const STORE_FLAG = "\x80";
    /**
     * BM25F weight factor for terms in title
     */
    const TITLE_WEIGHT = 4.0;
    /**
     * BM25F weight factor for terms in description
     */
    const DESCRIPTION_WEIGHT = 2.0;
    /**
     * BM25F weight factor for terms in a link
     */
    const LINK_WEIGHT = 1.0;
    /**
     * Stores document id's and links to documents id's together with
     * summary offset information, and number of words in the doc/link
     * The format for a record is 4 byte offset, followed by
     * 3 bytes for the document length, followed by 1 byte containing
     * the number of 8 byte doc key strings that make up the doc id (2 for
     * a doc, 3 for a link), followed by the doc key strings themselves.
     * In the case of a document the first doc key string has a hash of the
     * url, the second a hash a tag stripped version of the document.
     * In the case of a link, the keys are a unique identifier for the link
     * context, followed by  8 bytes for
     * the hash of the url being pointed to by the link, followed by 8
     * bytes for the hash of "info:url_pointed_to_by_link".
     * @var string
     */
    public $doc_infos;
    /**
     * Length of $doc_infos as a string
     * @var int
     */
    public $docids_len;
    /**
     * This string is non-empty when shard is loaded and in its packed state.
     * It consists of a sequence of posting records. Each posting
     * consists of a offset into the document entries structure
     * for a document containing the word this is the posting for,
     * as well as the number of occurrences of that word in that document.
     * @var string
     */
    public $word_docs;
    /**
     * Length of $word_docs as a string
     * @var int
     */
    public $word_docs_len;
    /**
     * Stores the array of word entries for this shard
     * In the packed state, word entries consist of the word id,
     * a generation number, an offset into the word_docs structure
     * where the posting list for that word begins,
     * and a length of this posting list. In the unpacked state
     * each entry is a string of all the posting items for that word
     * Periodically data in this words array is flattened to the word_postings
     * string which is a more memory efficient was of storing data in PHP
     * @var array
     */
    public $words;
    /**
     * Stores length of the words array in the shard on disk. Only set if
     * we're in $read_only_from_disk mode
     *
     * @var int
     */
     public $words_len;
    /**
     * An array representing offsets into the words dictionary of the index of
     * the first occurrence of a two byte prefix of a word_id.
     *
     * @var array
     */
    public $prefixes;
    /**
     * Length of the prefix index into the dictionary of the shard
     *
     * @var int
     */
    public $prefixes_len;
    /**
     * Number of documents (not links) stored in this shard
     * @var int
     */
    public $num_docs;
    /**
     * Keeps track of the number of documents a word is in
     * @var array
     */
    public $num_docs_word;
    /**
     * Number of links (not documents) stored in this shard
     * @var int
     */
    public $num_link_docs;
    /**
     * Number of words stored in total in all documents in this shard
     * @var int
     */
    public $len_all_docs;
    /**
     * Number of words stored in total in all links in this shard
     * @var int
     */
    public $len_all_link_docs;
    /**
     * File handle for a shard if we are going to use it in read mode
     * and not completely load it.
     *
     * @var resource
     */
    public $fh;
    /**
     * An cached array of disk blocks for an index shard that has not
     * been completely loaded into memory.
     * @var array
     */
    public $blocks;
    /**
     * Keeps track of the packed/unpacked state of the word_docs list
     *
     * @var bool
     */
    public $word_docs_packed;
    /**
     * Keeps track of the length of the shard as a file
     *
     * @var int
     */
    public $file_len;
    /**
     * Number of document inserts since the last time word data was flattened
     * to the word_postings string.
     * @var int
     */
     public $last_flattened_words_count;
    /**
     * Used to hold word_id, posting_len, posting triples as a memory efficient
     * string
     * @var string
     */
    public $word_postings;
    /**
     * Used to hold the computed 8 byte hash of the index shard filename
     * @var string
     */
    public $hash_name;
    /**
     * Stores $blocks contents in (32 bit) unsigned int
     * @var array
     */
    public $blocks_words;
    /**
     * Holds offset of the word_docs strings
     * @var int
     */
    public $word_doc_offset;
    /**
     * Holds offset of the doc_infos strings
     * @var int
     */
    public $doc_info_offset;
    /**
     * Makes an index shard with the given file name and generation offset
     *
     * @param string $fname filename to store the index shard with
     * @param int $generation when returning documents from the shard
     *      pretend there are this many earlier documents (the number
     *      of earlier shards, prior to the current shard)
     * @param int $num_docs_per_generation the number of documents
     *      that a given shard can hold
     * @param bool $read_only_from_disk used to determine if this
     *      shard is going to be largely kept on disk and to be in
     *      read only mode; otherwise, shard will assume to be
     *      completely held in memory and be read/writable
     */
    public function __construct($fname, public $generation = 0,
        public $num_docs_per_generation = C\NUM_DOCS_PER_PARTITION,
        public $read_only_from_disk = false)
    {
        parent::__construct($fname, -1);
        $this->hash_name = L\crawlHash($fname);
        $this->word_docs = "";
        $this->word_postings = "";
        $this->words_len = 0;
        $this->word_docs_len = 0;
        $this->last_flattened_words_count = 0;
        $this->words = [];
        $this->docids_len = 0;
        $this->doc_infos = "";
        $this->num_docs = 0;
        $this->num_link_docs = 0;
        $this->len_all_docs = 0;
        $this->len_all_link_docs = 0;
        $this->blocks = [];
        $this->fh = null;
        $this->word_docs_packed = false;
        $this->blocks_words= [];
    }
    /**
     * Used to pack a list of description scores and user ranks as a
     * string of auxiliary keys for a document map entry in the shard.
     * A document map entry consists of a four byte offset into a WebArchive,
     * three more bytes for the document length as, one byte for the
     * number of 8 byte aux keys, followed by a 24 byte key derived usually
     * from the url, host, etc, followed by the description scores,
     * user rank auxiliary keys.
     *
     * @param array $description_scores pairs position in document =>
     *      weight score that position got during summarization process.
     * @param array $user_ranks float scores gotten by a user classifier/ranker
     *      defined using Manage Classfiers.
     * @return string a string padded to length a multiple of 16 where
     *      @see packValues has been used to map each of the above array into a
     *      string
     */
    public function packAuxiliaryDocumentKeys($description_scores = [],
        $user_ranks = [])
    {
        $max_short = 2<<16 - 1;
        $aux_keys = "";
        $num_description_scores = count($description_scores);
        $num_ranks = count($user_ranks);
        if ($num_description_scores + $num_ranks > self::MAX_AUX_DOC_KEYS) {
            return $aux_keys;
        }
        $description_positions = ($num_description_scores > 0) ?
            L\deltaList(array_keys($description_scores)) : [];
        if ($num_description_scores > 0 && max($description_positions) <
            $max_short) {
            $aux_keys = "\xFF\xFF" . $this->packValues($description_positions) .
                $this->packValues($description_scores, "f");
        }
        if ($num_ranks > 0) {
            $aux_keys .= $this->packValues($user_ranks, "f");
        }
        $pad_len = 8 - (strlen($aux_keys) % 8);
        $padding = str_pad("", $pad_len, "\x00");
        return $aux_keys . $padding;
    }
    /**
     * Used to pack either an array of  nonnegative ints each less than
     * 65535 or array of floats. Pack is done into a string of 2 bytes/
     * entry shorts.
     * @param array $values nonnegative integers or floats to pack
     * @param string $type if is "i" then assuming integers we are packing
     *      otherwise floats
     * @return string with packed values
     */
    public function packValues($values, $type = "i")
    {
        $num_values = count($values);
        if ($type == "i") {
            array_unshift($values, $num_values);
            array_unshift($values, "S*");
            return call_user_func_array("pack", $values);
        }
        $max_short = 2<<16 - 1;
        $max_minus_one = $max_short - 1;
        $packed_values = pack("S", $num_values);
        foreach ($values as $key => $value) {
            $short_value = floor($value * $max_short);
            if ($short_value > $max_minus_one) {
                $short_value = $max_minus_one;
            }
            $packed_values .= pack("S", $short_value);
        }
        return $packed_values;
    }
    /**
     * Add a new document to the index shard with the given summary offset.
     * Associate with this document the supplied list of words and word counts.
     * Finally, associate the given meta words with this document.
     *
     * @param string $doc_keys a string of concatenated keys for a document
     *     to insert. Each key is assumed to be a string of DOC_KEY_LEN many
     *     bytes. This whole set of keys is viewed as fixing one document.
     * @param int $summary_offset its offset into the word archive the
     *     document's data is stored in
     * @param array $word_lists (word => array of word positions in doc)
     * @param array $meta_ids meta words to be associated with the document
     *     an example meta word would be filetype:pdf for a PDF document.
     * @param bool $is_doc flag used to indicate if what is being scored is
     *     a document or a link to a document
     * @param mixed $rank either false if not used, or a 4 bit estimate of the
     *     rank of this document item
     * @param array $description_scores per-position importance weights
     *     for the description text (map position -> 0..15 score) used
     *     for boosting summary terms in scoring
     * @param array $user_ranks per-classifier rank contributions
     *     (map classifier_label -> 0..15 score) appended to the
     *     auxiliary doc-key block
     * @return bool success or failure of performing the add
     */
    public function addDocumentWords($doc_keys, $summary_offset, $word_lists,
        $meta_ids = [], $is_doc = false, $rank = false,
        $description_scores = [], $user_ranks = [])
    {
        if ($this->word_docs_packed == true) {
            $this->words = [];
            $this->word_docs = "";
            $this->word_docs_packed = false;
        }
        $doc_len = 0;
        $link_doc_len = 0;
        $doc_keys .= $this->packAuxiliaryDocumentKeys($description_scores,
            $user_ranks);
        $len_key = strlen($doc_keys);
        $num_keys = floor($len_key/self::DOC_KEY_LEN);
        if ($num_keys * self::DOC_KEY_LEN != $len_key) {
            return false;
        }
        if ($num_keys % 2 == 0 ) {
            $doc_keys .= self::BLANK; //want to keep docids_len divisible by 16
        }
        $summary_offset_string = L\packInt($summary_offset);
        $added_len = strlen($summary_offset_string);
        $this->doc_infos .= $summary_offset_string;
        if ($is_doc) {
            $this->num_docs++;
        } else { //link item
            $this->num_link_docs++;
        }
        foreach ($meta_ids as $meta_id) {
            $word_lists[$meta_id] = [];
        }
        //using $this->docids_len divisible by 16
        $doc_offset = $this->docids_len >> 4;
        foreach ($word_lists as $word => $position_list) {
            $word_id = L\crawlHashWord($word, true);
            $occurrences = count($position_list);
            $store = L\packPosting($doc_offset, $position_list);
            if (!isset($this->words[$word_id])) {
                $this->words[$word_id] = $store;
            } else {
                $this->words[$word_id] .= $store;
            }
            if (!isset($this->num_docs_word[$word_id])) {
                $this->num_docs_word[$word_id] = 1;
            } else {
                $this->num_docs_word[$word_id]++;
            }
            if ($occurrences > 0) {
                if ($is_doc == true) {
                    $doc_len += $occurrences;
                } else {
                    $link_doc_len += $occurrences;
                }
            }
            $this->word_docs_len += strlen($store);
        }
        $this->len_all_docs += $doc_len;
        $this->len_all_link_docs += $link_doc_len;
        $flags = ($is_doc) ? 0 : self::LINK_FLAG;
        if ($rank !== false) {
            $rank &= 0x0f;
            $rank <<= 19;
            $flags += $rank;
        }
        $item_len = ($is_doc) ? $doc_len: $link_doc_len;
        $len_num_keys = (L\packInt(((($flags + $item_len)) << 8) + $num_keys));
        $this->doc_infos .=  $len_num_keys;
        $added_len += strlen($len_num_keys);
        $this->doc_infos .= $doc_keys;
        $added_len += strlen($doc_keys);
        $this->docids_len += $added_len;
        return true;
    }
    /**
     * Returns the first offset, last offset, and number of documents the
     * word occurred in for this shard. The first offset (similarly, the last
     * offset) is the byte offset into the word_docs string of the first
     * (last) record involving that word.
     *
     * @param string $word_id id of the word one wants to look up
     * @param bool $raw whether the id is our version of base64 encoded or not
     * @return array first offset, last offset, count, exact matching id
     */
    public function getWordInfo($word_id, $raw = false)
    {
        if ($raw == false) {
            //get rid of out modified base64 encoding
            $word_id = L\unbase64Hash($word_id);
        }
        $is_disk = $this->read_only_from_disk;
        $word_item_len = self::WORD_KEY_LEN + self::WORD_DATA_LEN;
        $word_key_len = self::WORD_KEY_LEN;
        if ($is_disk) {
            $this->readShardHeader();
            if (!isset($word_id[1])) {
                return false;
            }
            $prefix = (ord($word_id[0]) << 8) + ord($word_id[1]);
            $prefix_info = $this->getShardSubstring(
                self::HEADER_LENGTH + 8 * $prefix, 8);
            if ($prefix_info == self::BLANK || !isset($prefix_info[2])) {
                return false;
            }
            list(,$offset, $high) = unpack("N*", $prefix_info);
            $high--;
            $start = self::HEADER_LENGTH + $this->prefixes_len  + $offset;
        } else {
            if ($this->word_docs_packed == false) {
                $this->mergeWordPostingsToString();
                $this->packWords(null);
                $this->outputPostingLists();
            }
            $start = 0;
            $high = (strlen($this->words) - $word_item_len)/$word_item_len;
        }
        $low = 0;
        $check_loc = (($low + $high) >> 1);
        do {
            $old_check_loc = $check_loc;
            $word_string = $this->getWordString($is_disk, $start, $check_loc,
                $word_item_len);
            if ($word_string == false) {
                return false;
            }
            $id = substr($word_string, 0, $word_key_len);
            $cmp = L\compareWordHashes($word_id, $id);
            if ($cmp === 0) {
                $tmp_info = $this->getWordInfoFromString(
                    substr($word_string, $word_key_len));
                $tmp_info[] = $id;
                return $tmp_info;
            } else if ($cmp < 0) {
                $high = $check_loc;
                $check_loc = (($low + $check_loc) >> 1);
            } else {
                if ($check_loc + 1 == $high) {
                    $check_loc++;
                }
                $low = $check_loc;
                $check_loc = (($high + $check_loc) >> 1);
            }
        } while($old_check_loc != $check_loc);
        return false;
    }
    /**
     *  Return word record (word key + posting lookup data )from the shard
     *  from the shard posting list
     *
     * @param bool $is_disk whether the shard is on disk or in memory
     * @param int $start offset to start of the dictionary
     * @param int $location index of record to extract from dictionary
     * @param int $word_item_len length of a word + data record
     * @return string the word-key-plus-posting-lookup record at the given
     *      slot, read from disk or from the in-memory dictionary
     */
    function getWordString($is_disk, $start, $location, $word_item_len)
    {
        if ($is_disk) {
            $word_string = $this->getShardSubstring($start +
                $location * $word_item_len, $word_item_len);
        } else {
            $word_string = substr($this->words, $start +
                $location * $word_item_len, $word_item_len);
        }
        return $word_string;
    }
    /**
     * Used to flatten the words associative array to a more memory
     * efficient word_postings string.
     *
     * $this->words is an associative array with associations
     *     wordid => postinglistforid
     * this format is relatively wasteful of memory
     *
     * $this->word_postings is a string in the format
     *     wordid1len1postings1wordid2len2postings2 ...
     * wordids are lex ordered. This is more memory efficient as the
     * former relies on the more wasteful php implementation of associative
     * arrays.
     *
     * mergeWordPostingsToString converts the former format to the latter
     * for each of the current wordids. $this->words is then set to [];
     * Note before this operation is done $this->word_postings might have
     * data from earlier times mergeWordPostingsToString was called, in which
     * case the behavior is controlled by $replace.
     *
     * @param bool $replace whether to overwrite existing word_id postings
     *    (true) or to append (false)
     */
    public function mergeWordPostingsToString($replace = false)
    {
        if ($this->word_docs_packed) {
            return;
        }
        L\crawlLog("Merge index shard postings to string to save memory.");
        ksort($this->words, SORT_STRING);
        $tmp_string = "";
        $offset = 0;
        $write_offset = 0;
        $len = strlen($this->word_postings);
        $key_len = self::WORD_KEY_LEN;
        $posting_len = self::POSTING_LEN;
        $item_len = $key_len + $posting_len;
        $num_words = count($this->words);
        $i = 0;
        foreach ($this->words as $word_id => $postings) {
            $cmp = -1;
            while($cmp < 0 && $offset + $item_len <= $len) {
                L\crawlTimeoutLog("..merging index word postings to string ..".
                    " processing %s of %s at offset %s less than %s", $i,
                    $num_words, $offset, $len);
                $key = substr($this->word_postings, $offset, $key_len);
                $pack_key_posts_len = substr(
                    $this->word_postings, $offset + $key_len, $posting_len);
                $key_posts_len = L\unpackInt($pack_key_posts_len);
                $key_postings = substr($this->word_postings,
                    $offset + $item_len, $key_posts_len);
                $word_id_posts_len = strlen($postings);
                $cmp = strcmp($key, $word_id);
                if ($cmp == 0) {
                    if ($replace) {
                        $tmp_string .= $key .
                            L\packInt($word_id_posts_len) . $postings;
                    } else {
                        $tmp_string .= $key .
                            L\packInt($key_posts_len + $word_id_posts_len) .
                            $key_postings . $postings;
                        $offset += $item_len + $key_posts_len;
                    }
                } else if ($cmp < 0) {
                    $tmp_string .= $key .$pack_key_posts_len. $key_postings;
                    $offset += $item_len + $key_posts_len;
                } else {
                    $tmp_string .= $word_id .
                        L\packInt($word_id_posts_len). $postings;
                }
                $tmp_len = strlen($tmp_string);
                $copy_data_len = min(self::WORD_POSTING_COPY_LEN, $tmp_len);
                $copy_to_len = min($offset - $write_offset,
                    $len - $write_offset);
                if ($copy_to_len > $copy_data_len  &&
                    $tmp_len > $copy_data_len) {
                    L\charCopy($tmp_string, $this->word_postings, $write_offset,
                        $copy_data_len, "merge index charCopy 1");
                    $write_offset += $copy_data_len;
                    $tmp_string = substr($tmp_string, $copy_data_len);
                }
           }
           L\crawlTimeoutLog("..outer loop merge index postings to string ..".
                " processing %s of %s.", $i, $num_words);
           if ($offset + $item_len > $len) {
                $word_id_posts_len = strlen($postings);
                if ($write_offset < $len) {
                    $tmp_len = strlen($tmp_string);
                    $copy_data_len = $len - $write_offset;
                    if ($tmp_len < $copy_data_len) {//this case shouldn't occur
                        $this->word_postings =
                            substr($this->word_postings, 0, $write_offset);
                        $this->word_postings .= $tmp_string;
                    } else {
                        L\charCopy($tmp_string, $this->word_postings,
                            $write_offset, $copy_data_len,
                            "merge index charCopy 2");
                        $tmp_string = substr($tmp_string, $copy_data_len);
                        $this->word_postings .= $tmp_string;
                    }
                    $tmp_string = "";
                    $write_offset = $len;
                }
                $this->word_postings .=
                    $word_id . L\packInt($word_id_posts_len). $postings;
            }
            $i++;
        }
        L\crawlLog("..Merge Index Posting Final Copy");
        $this->words = [];
        // garbage collection may take a while, call with true so don't time out
        CrawlDaemon::processHandler(true);
        if ($tmp_string != "") {
            L\crawlLog("..Merge Index Posting Final Copy 1 ".
                "Current Memory: ". memory_get_usage());
            $tmp_string .= substr($this->word_postings, $offset);
            L\crawlLog("..Merge Index Posting Final Copy 2 ".
                "Current Memory: ". memory_get_usage());
            $this->word_postings = substr($this->word_postings, 0,
                $write_offset);
            L\crawlLog("..Merge Index Posting Final Copy 3 ".
                "Current Memory: ". memory_get_usage());
            $this->word_postings .= $tmp_string;
        }
        $this->last_flattened_words_count = $this->num_docs;
        L\crawlLog("..Done Merge Index Posting Final Copy");
    }
    /**
     * Save the IndexShard to its filename
     *
     * @param bool $to_string whether output should be written to a string
     *     rather than the default file location
     * @param bool $with_logging whether log messages should be written
     *     as the shard save progresses
     * @return string serialized shard if output was to string else empty
     *     string
     */
    public function save($to_string = false, $with_logging = false)
    {
        $out = "";
        $this->mergeWordPostingsToString();
        if ($with_logging) {
            L\crawlLog("Saving index shard .. done merge postings to string");
        }
        $this->prepareWordsAndPrefixes($with_logging);
        if ($with_logging) {
            L\crawlLog("Saving index shard .. make prefixes");
        }
        $header =  pack("N*", $this->prefixes_len,
            $this->words_len,
            $this->word_docs_len,
            $this->docids_len,
            $this->generation,
            $this->num_docs_per_generation,
            $this->num_docs,
            $this->num_link_docs,
            $this->len_all_docs,
            $this->len_all_link_docs);
        if ($with_logging) {
            L\crawlLog("Saving index shard .. packed header");
        }
        if ($to_string) {
            $out = $header;
            $this->packWords(null);
            $out .= $this->words;
            $this->outputPostingLists(null, $with_logging);
            $out .= $this->word_docs;
            $out .= $this->doc_infos;
        } else {
            $fh = fopen($this->filename, "wb");
            fwrite($fh, $header);
            fwrite($fh, $this->prefixes);
            $this->packWords($fh, $with_logging);
            if ($with_logging) {
                L\crawlLog("Saving index shard .. wrote dictionary");
            }
            $this->outputPostingLists($fh, $with_logging);
            if ($with_logging) {
                L\crawlLog("Saving index shard .. wrote postings lists");
            }
            fwrite($fh, $this->doc_infos);
            fclose($fh);
        }
        if ($with_logging) {
            L\crawlLog("Saving index shard .. wrote doc map. Done save");
        }
        // clean up by returning to state where could add more docs
        $this->words = [];
        $this->word_docs = "";
        $this->prefixes = "";
        $this->word_docs_packed = false;
        return $out;
    }
    /**
     * This method re-saves a saved shard without the prefixes and dictionary.
     * It would typically be called after this information has been stored
     * in an IndexDictionary obbject so that the data is not redundantly stored
     * @param bool $with_logging whether log messages should be written
     *     as the shard save progresses
     */
    public function saveWithoutDictionary($with_logging = false)
    {
        $this->readShardHeader(true);
        if ($with_logging) {
            L\crawlLog(
                "Opening without dictionary version of shard to write...");
        }
        $fh = fopen($this->filename . "-tmp", "wb");
        $header =  pack("N*", 0, 0,
            $this->word_docs_len,
            $this->docids_len,
            $this->generation,
            $this->num_docs_per_generation,
            $this->num_docs,
            $this->num_link_docs,
            $this->len_all_docs,
            $this->len_all_link_docs);
        fwrite($fh, $header);
        if ($with_logging) {
            L\crawlLog("..without dictionary version of shard header written");
        }
        if (!$this->read_only_from_disk) {
            $this->packWords(null, $with_logging);
        }
        $remaining = $this->word_docs_len;
        $offset = 0;
        $buffer_size = 16 * self::SHARD_BLOCK_SIZE;
        while ($remaining > 0) {
            $len = min($remaining, $buffer_size);
            $data = $this->getWordDocsSubstring($offset, $len, false);
            fwrite($fh, $data);
            $offset += $len;
            $remaining -= $len;
        }
        if ($with_logging) {
            L\crawlLog(
                "..without dictionary version of shard word docs written");
        }
        $remaining = $this->docids_len;
        $offset = 0;
        while ($remaining > 0) {
            $len = min($remaining, $buffer_size);
            $data = $this->getDocInfoSubstring($offset, $len, false);
            fwrite($fh, $data);
            $offset += $len;
            $remaining -= $len;
        }
        if ($with_logging) {
            L\crawlLog(
                "..without dictionary version of shard doc infos written");
        }
        fclose($fh);
        if (file_exists($this->filename . "-tmp")) {
            if (!empty($this->fh)) {
                fclose($this->fh);
            }
            unlink($this->filename);
            rename($this->filename . "-tmp", $this->filename);
        }
        if ($with_logging) {
            L\crawlLog("done replacing version of shard.");
        }
    }
    /**
     * Computes the prefix string index for the current words array.
     * This index gives offsets of the first occurrences of the lead two char's
     * of a word_id in the words array. This method assumes that the word
     * data is already in >word_postings
     * @param bool $with_logging whether log messages should be written
     *     as progresses
     */
    public function prepareWordsAndPrefixes($with_logging = false)
    {
        $word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
        $key_len = self::WORD_KEY_LEN;
        $posting_len = self::POSTING_LEN;
        $this->words_len = 0;
        $word_postings_len = strlen($this->word_postings);
        $pos = 0;
        $tmp = [];
        $offset = 0;
        $num_words = 0;
        $old_prefix = false;
        while($pos < $word_postings_len) {
            if ($with_logging) {
                L\crawlTimeoutLog("..Outputting to position %s of" .
                    " %s of prefixes.", $pos, $word_postings_len);
            }
            $this->words_len += $word_item_len;
            $first = substr($this->word_postings, $pos, $key_len);
            $post_len = L\unpackInt(substr($this->word_postings,
                $pos + $key_len, $posting_len));
            $pos += $key_len + $posting_len + $post_len;
            $prefix = (ord($first[0]) << 8) + ord($first[1]);
            if ($old_prefix === $prefix) {
                $num_words++;
            } else {
                if ($old_prefix !== false) {
                    $tmp[$old_prefix] = pack("N*", $offset, $num_words);
                    $offset += $num_words * $word_item_len;
                }
                $old_prefix = $prefix;
                $num_words = 1;
            }
        }
        $tmp[$old_prefix] = pack("N*", $offset, $num_words);
        $num_prefixes = 2 << 16;
        $this->prefixes = "";
        for ($i = 0; $i < $num_prefixes; $i++) {
            if (isset($tmp[$i])) {
                $this->prefixes .= $tmp[$i];
            } else {
                $this->prefixes .= self::BLANK;
            }
        }
        $this->prefixes_len = strlen($this->prefixes);
    }
    /**
     * Posting lists are initially stored associated with a word as a key
     * value pair. The merge operation then merges them these to a string
     * by word_postings. packWords separates words from postings.
     * After being applied words is a string consisting of
     * triples (as concatenated strings) word_id, start_offset, end_offset.
     * The offsets refer to integers offsets into a string $this->word_docs
     * Finally, if a file handle is given, it writes the word dictionary out
     * to the file as a long string. This function assumes
     * mergeWordPostingsToString has just been called.
     *
     * @param resource $fh a file handle to write the dictionary to, if desired
     * @param bool $with_logging whether to write progress log messages every
     *     30 seconds
     */
    public function packWords($fh = null, $with_logging = false)
    {
        if ($this->word_docs_packed) {
            return;
        }
        $word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
        $key_len = self::WORD_KEY_LEN;
        $posting_len = self::POSTING_LEN;
        $this->word_docs_len = 0;
        $this->words = "";
        $total_out = "";
        $word_postings_len = strlen($this->word_postings);
        $pos = 0;
        $two_doc_len = 2 * self::DOC_KEY_LEN;
        while($pos < $word_postings_len) {
            if ($with_logging) {
                L\crawlTimeoutLog("..packing index shard words at %s of %s.",
                    $pos, $word_postings_len);
            }
            $word_id = substr($this->word_postings, $pos, $key_len);
            $len = L\unpackInt(substr($this->word_postings,
                $pos + $key_len, $posting_len));
            if (!isset($this->num_docs_word[$word_id])) {
                L\crawlLog("No number count in index for " .
                    L\toHexString($word_id));
                $this->num_docs_word[$word_id] = ($len >> 2);
            }
            $num_docs_word = $this->num_docs_word[$word_id];
            $postings = substr($this->word_postings,
                $pos + $key_len + $posting_len, $len);
            $pos += $key_len + $posting_len + $len;
            /*
                we pack generation info to make it easier to build the global
                dictionary
            */
            if ($len != $two_doc_len ||
                strncmp($postings, self::HALF_BLANK, self::POSTING_LEN) != 0) {
                /* if len is small code count in high order half word.
                   In my experimentation all but a 100 or so word counts out of
                   all the words in 40000 or so docs can be coded in this way
                 */
                $orig_len = $len;
                if ($len < 32767 && $num_docs_word <= $len) {
                    $len += ($num_docs_word << 16) + (1 << 31);
                }
                $out = pack("N*", $this->generation, $this->word_docs_len,
                    $len);
                $this->word_docs_len += $orig_len;
                $this->words .= $word_id . $out;
            } else {
                /* single occurrence case - high word blank except high bit,
                   low word has posting (so don't go to posting list,
                   operate only in dictionary)
                 */
                $out = substr($postings,
                    self::POSTING_LEN, $word_item_len);
                $out[0] = chr((0x80 | ord($out[0])));
                $this->words .= $word_id . $out;
            }
        }
        if ($fh != null) {
            fwrite($fh, $this->words);
        }
        $this->words_len = strlen($this->words);
        $this->word_docs_packed = true;
    }
    /**
     * Used to convert the word_postings string into a word_docs string
     * or if a file handle is provided write out the word_docs sequence
     * of postings to the provided file handle.
     *
     * @param resource $fh a filehandle to write to
     * @param bool $with_logging whether to log progress
     */
    public function outputPostingLists($fh = null, $with_logging = false)
    {
        $word_item_len = IndexShard::WORD_KEY_LEN + IndexShard::WORD_DATA_LEN;
        $key_len = self::WORD_KEY_LEN;
        $posting_len = self::POSTING_LEN;
        $this->word_docs = "";
        $total_out = "";
        $word_postings_len = strlen($this->word_postings);
        $pos = 0;
        $tmp_string = "";
        $tmp_len = 0;
        $two_doc_len = 2 * self::DOC_KEY_LEN;
        while($pos < $word_postings_len) {
            if ($with_logging) {
                L\crawlTimeoutLog("..Outputting to position %s of" .
                    " %s in posting lists.", $pos,
                    $word_postings_len);
            }
            $word_id = substr($this->word_postings, $pos, $key_len);
            $len = L\unpackInt(substr($this->word_postings,
                $pos + $key_len, $posting_len));
            $postings = substr($this->word_postings,
                $pos + $key_len + $posting_len, $len);
            $pos += $key_len + $posting_len + $len;
            if ($len != $two_doc_len ||
                strncmp($postings,  self::HALF_BLANK, self::POSTING_LEN) != 0) {
                if ($fh != null) {
                    if ($tmp_len < self::SHARD_BLOCK_SIZE) {
                        $tmp_string .= $postings;
                        $tmp_len += $len;
                    } else {
                        fwrite($fh, $tmp_string);
                        $tmp_string = $postings;
                        $tmp_len = $len;
                    }
                } else {
                    $this->word_docs .= $postings;
                }
           }
        }
        if ($tmp_len > 0) {
            if ($fh == null ) {
                $this->word_docs .= $tmp_string;
            } else {
                fwrite($fh, $tmp_string);
            }
        }
    }
    /**
     * Takes the word docs string and splits it into posting lists which are
     * assigned to particular words in the words dictionary array.
     * This method is memory expensive as it briefly has essentially
     * two copies of what's in word_docs.
     */
    public function unpackWordDocs()
    {
        if (!$this->word_docs_packed) {
            return;
        }
        $num_lists = count($this->words);
        $cnt = 0;
        foreach ($this->words as $word_id => $postings_info) {
            /* we are ignoring the first four bytes which contains
               generation info
             */
            L\crawlTimeoutLog("..still unpacking index posting lists. At" .
                " list %s of %s.", $cnt, $num_lists);
            if ((ord($postings_info[0]) & 0x80) > 0 ) {
                $postings_info[0] = chr(ord($postings_info[0]) - 0x80);
                $postings_info = self::HALF_BLANK . $postings_info;
                $this->words[$word_id] = $postings_info;
                $this->num_docs_word[$word_id] = 1;
            } else {
                $tmp = unpack("N*", substr($postings_info, 4,
                    8));
                if (!isset($tmp[2])) {
                    continue;
                }
                list(, $offset, $len) = $tmp;
                if (($len & (1 << 31))) {
                    $this->num_docs_word[$word_id] = (($len >> 16) & 32767);
                    $len = ($len & 65535);
                } else {
                    //only approximate assuming each posting 4 bytes
                    $this->num_docs_word[$word_id] = $len >> 2;
                }
                $postings = substr($this->word_docs, $offset, $len);
                $this->words[$word_id] = $postings;
            }
            $cnt++;
        }
        unset($this->word_docs);
        $this->word_docs_packed = false;
    }
    /**
     * From disk gets $len many bytes starting from $offset in the word_docs
     * strings
     *
     * @param $offset byte offset to begin getting data out of disk-based
     *     word_docs
     * @param $len number of bytes to get
     * @param bool $cache whether to cache disk blocks read from disk
     * @return desired string
     */
    public function getWordDocsSubstring($offset = 0, $len = 0, $cache = true)
    {
        if ($len <= 0) {
            $len = $this->word_docs_len;
        }
        if ($this->read_only_from_disk) {
            return $this->getShardSubstring($this->word_doc_offset + $offset,
                $len, $cache);
        }
        return substr($this->word_docs, $offset, $len);
    }
    /**
     * From disk gets $len many bytes starting from $offset in the doc_infos
     * strings
     *
     * @param $offset byte offset to begin getting data out of disk-based
     *     doc_infos
     * @param $len number of bytes to get
     * @param bool $cache whether to cache disk blocks read from disk
     * @return string desired
     */
    public function getDocInfoSubstring($offset = 0, $len = 0, $cache = false)
    {
        if ($len <= 0) {
            $len = $this->docids_len;
        }
        if ($this->read_only_from_disk) {
            return $this->getShardSubstring(
                $this->doc_info_offset + $offset, $len, $cache);
        }
        return substr($this->doc_infos, $offset, $len);
    }
    /**
     * Gets from Disk Data $len many bytes beginning at $offset from the
     * current IndexShard
     *
     * @param int $offset byte offset to start reading from
     * @param int $len number of bytes to read
     * @param bool $cache whether to cache disk blocks read from disk
     * @return string data from that location  in the shard
     */
    public function getShardSubstring($offset, $len, $cache = true)
    {
        $block_offset =  ($offset >> self::SHARD_BLOCK_POWER)
            << self::SHARD_BLOCK_POWER;
        $start_loc = $offset - $block_offset;
        //if all in one block do it quickly
        if ($start_loc + $len < self::SHARD_BLOCK_SIZE) {
            return substr($this->readBlockShardAtOffset($block_offset, $cache),
                $start_loc, $len);
        }
        // otherwise, this loop is slower, but handles general case
        $data = $this->readBlockShardAtOffset($block_offset, $cache);
        if ($data === false) {
            return "";
        }
        $substring = substr($data, $start_loc);
        $block_size = self::SHARD_BLOCK_SIZE;
        $block_offset += $block_size;
        while (strlen($substring) < $len) {
            $data = $this->readBlockShardAtOffset($block_offset, $cache);
            if ($data === false) {
                return $substring;
            }
            $block_offset += $block_size;
            $substring .= $data;
        }
        return substr($substring, 0, $len);
    }
    /**
     * Reads SHARD_BLOCK_SIZE from the current IndexShard's file beginning
     * at byte offset $bytes
     *
     * @param int $bytes byte offset to start reading from
     * @param bool $cache whether to cache disk blocks that have been read to
     *     RAM
     * @return mixed data fromIndexShard file if found, false otherwise
     */
    public function readBlockShardAtOffset($bytes, $cache = true)
    {
        if (isset($this->blocks[$bytes]) && $cache) {
            return $this->blocks[$bytes];
        }
        if ($this->fh === null) {
            if (!file_exists($this->filename)) {
                return false;
            }
            $this->fh = fopen($this->filename, "rb");
            if ($this->fh === false) {
                return false;
            }
            $this->file_len = filesize($this->filename);
        }
        if ($bytes >= $this->file_len) {
            return false;
        }
        $seek = fseek($this->fh, $bytes, SEEK_SET);
        if ($seek < 0) {
            return false;
        }
        if (!$cache) {
            return fread($this->fh, self::SHARD_BLOCK_SIZE);
        }
        if (count($this->blocks) > self::SHARD_BLOCK_SIZE) {
            $this->blocks = [];
            $this->blocks_words = [];
        }
        $this->blocks[$bytes] = fread($this->fh, self::SHARD_BLOCK_SIZE);
        $tmp = & $this->blocks[$bytes];
        $this->blocks_words += array_combine(
            range($bytes, $bytes + strlen($tmp) - 1, 4),
            unpack("N*", $tmp));
        return $tmp;
    }
    /**
     * If not already loaded, reads in from disk the fixed-length'd field
     * variables of this IndexShard ($this->words_len, etc)
     * @param bool $force If true
     * @return bool whether was able to read in or not
     */
    public function readShardHeader($force = false)
    {
        if (!empty($this->num_docs) && $this->num_docs > 0 && !$force) {
            return true; // if $this->num_docs > 0 assume have read in
        }
        $header = substr($this->readBlockShardAtOffset(0, false),
            0, self::HEADER_LENGTH);
        if (!$header) {
            return false;
        }
        self::headerToShardFields($header, $this);
        $this->doc_info_offset = $this->file_len - $this->docids_len;
        return true;
    }
    /**
     * Converts $str into 3 ints for a first offset into word_docs,
     * a last offset into word_docs, and a count of number of docs
     * with that word.
     *
     * @param string $str 12 or 16-byte packed binary string read out
     *      of a dictionary entry
     * @param bool $include_generation when true the generation number
     *      is prepended to the returned tuple (used by callers that
     *      walk a posting list across generations); when false (default)
     *      only the three offset/len/count ints are returned
     * @return array of these three or four int's
     */
    public static function getWordInfoFromString($str,
        $include_generation = false)
    {
        list(, $generation, $first_offset, $len) = unpack("N*", $str);
        $orig = $len;
        if (($len & (1 << 31))) {
            $count = (($len >> 16) & 32767);
            $len = ($len & 65535);
        } else {
            $count = $len >> 2;
        }
        $last_offset = $first_offset + $len - self::POSTING_LEN;
        if ($include_generation) {
            return [$generation, $first_offset, $last_offset, $count];
        }
        return [$first_offset, $last_offset, $count];
    }
    /**
     * Load an IndexShard from a file or string
     *
     * @param string $fname the name of the file to the IndexShard from/to
     * @param string &$data stringified shard data to load shard from. If null
     *     then the data is loaded from the $fname if possible
     * @return IndexShard the IndexShard loaded
     */
    public static function load($fname, &$data = null)
    {
        L\crawlLog("Loading index shard $fname");
        $shard = new IndexShard($fname);
        if ($data === null) {
            $fh = fopen($fname, "rb");
            $shard->file_len = filesize($fname);
            $header = fread($fh, self::HEADER_LENGTH);
        } else {
            $shard->file_len = strlen($data);
            $header = substr($data, 0, self::HEADER_LENGTH);
            $pos = self::HEADER_LENGTH;
        }
        self::headerToShardFields($header, $shard);
        L\crawlLog("..done reading index shard header");
        if ($data === null) {
            if (!($shard->prefixes_len > 0 ) || !($shard->words_len > 0 ) ||
                !($shard->word_docs_len > 0 )|| !($shard->docids_len > 0 ) ) {
                fclose($fh);
                return null;
            }
            fread($fh, $shard->prefixes_len);
            $words = fread($fh, $shard->words_len);
            $shard->word_docs = fread($fh, $shard->word_docs_len);
            $shard->doc_infos = fread($fh, $shard->docids_len);
            fclose($fh);
        } else {
            $words = substr($data, $pos, $shard->words_len);
            $pos += $shard->words_len;
            $shard->word_docs = substr($data, $pos, $shard->word_docs_len);
            $pos += $shard->word_docs_len;
            $shard->doc_infos = substr($data, $pos, $shard->docids_len);
        }
        $pre_words_array = str_split($words, self::WORD_KEY_LEN +
            self::WORD_DATA_LEN);
        unset($words);
        $make_words = C\NS_LIB . 'storage_formats\\IndexShard::makeWords';
        array_walk($pre_words_array, $make_words,
            $shard);
        L\crawlLog("..done reading making index shard word structure");
        $shard->word_docs_packed = true;
        $shard->unpackWordDocs();
        L\crawlLog("..done unpacking index shard posting lists");
        return $shard;
    }
    /**
     * Split a header string into a shards field variable
     *
     * @param string $header a string with packed shard header data
     * @param object $shard IndexShard to put data into
     */
    public static function headerToShardFields($header, $shard)
    {
        list(,
            $shard->prefixes_len,
            $shard->words_len,
            $shard->word_docs_len,
            $shard->docids_len,
            $shard->generation,
            $shard->num_docs_per_generation,
            $shard->num_docs,
            $shard->num_link_docs,
            $shard->len_all_docs,
            $shard->len_all_link_docs
            ) = unpack("N*", $header);
        $shard->word_doc_offset = self::HEADER_LENGTH +
            $shard->prefixes_len + $shard->words_len;
    }
    /**
     * Callback function for load method. splits a word_key . word_info string
     * into an entry in the passed shard $shard->words[word_key] = $word_info.
     *
     * @param string &$value  the word_key . word_info string
     * @param int $key index in array - we don't use
     * @param object $shard IndexShard to add the entry to word table for
     */
    public static function makeWords(&$value, $key, $shard)
    {
        $shard->words[substr($value, 0, self::WORD_KEY_LEN)] =
            substr($value, self::WORD_KEY_LEN,
                self::WORD_DATA_LEN);
    }
}
