Feature: highlight fulltext search results

How it works:

  1. when a fulltext search is made, Shaarli looks for the first
occurence position of every term matching the search. No change here,
but we store these positions in an array, in Bookmark's additionalContent.
  2. when formatting bookmarks (through BookmarkFormatter
implementation):
    1. first we insert specific tokens at every search result positions
    2. we format the content (escape HTML, apply markdown, etc.)
    3. as a last step, we replace our token with displayable span
elements

Cons: this tightens coupling between search filters and formatters
Pros: it was absolutely necessary not to perform the
search twice. this solution has close to no impact on performances.

Fixes #205

2 files changed, 139 insertions, 18 deletions

diff --git a/application/bookmark/Bookmark.php b/application/bookmark/Bookmark.php
index fa45d2fc..ea565d1f 100644
--- a/application/bookmark/Bookmark.php
+++ b/application/bookmark/Bookmark.php
@@ -54,6 +54,9 @@ class Bookmark
     /** @var bool True if the bookmark can only be seen while logged in */
     protected $private;
 
+    /** @var mixed[] Available to store any additional content for a bookmark. Currently used for search highlight. */
+    protected $additionalContent = [];
+
     /**
      * Initialize a link from array data. Especially useful to create a Bookmark from former link storage format.
      *
@@ -95,6 +98,8 @@ class Bookmark
      *   - the URL with the permalink
      *   - the title with the URL
      *
+     * Also make sure that we do not save search highlights in the datastore.
+     *
      * @throws InvalidBookmarkException
      */
     public function validate(): void
@@ -112,6 +117,9 @@ class Bookmark
         if (empty($this->title)) {
             $this->title = $this->url;
         }
+        if (array_key_exists('search_highlight', $this->additionalContent)) {
+            unset($this->additionalContent['search_highlight']);
+        }
     }
 
     /**
@@ -436,6 +444,44 @@ class Bookmark
     }
 
     /**
+     * Get entire additionalContent array.
+     *
+     * @return mixed[]
+     */
+    public function getAdditionalContent(): array
+    {
+        return $this->additionalContent;
+    }
+
+    /**
+     * Set a single entry in additionalContent, by key.
+     *
+     * @param string     $key
+     * @param mixed|null $value Any type of value can be set.
+     *
+     * @return $this
+     */
+    public function addAdditionalContentEntry(string $key, $value): self
+    {
+        $this->additionalContent[$key] = $value;
+
+        return $this;
+    }
+
+    /**
+     * Get a single entry in additionalContent, by key.
+     *
+     * @param string $key
+     * @param mixed|null $default
+     *
+     * @return mixed|null can be any type or even null.
+     */
+    public function getAdditionalContentEntry(string $key, $default = null)
+    {
+        return array_key_exists($key, $this->additionalContent) ? $this->additionalContent[$key] : $default;
+    }
+
+    /**
      * Rename a tag in tags list.
      *
      * @param string $fromTag
diff --git a/application/bookmark/BookmarkFilter.php b/application/bookmark/BookmarkFilter.php
index 4232f114..c79386ea 100644
--- a/application/bookmark/BookmarkFilter.php
+++ b/application/bookmark/BookmarkFilter.php
@@ -201,7 +201,7 @@ class BookmarkFilter
             return $this->noFilter($visibility);
         }
 
-        $filtered = array();
+        $filtered = [];
         $search = mb_convert_case(html_entity_decode($searchterms), MB_CASE_LOWER, 'UTF-8');
         $exactRegex = '/"([^"]+)"/';
         // Retrieve exact search terms.
@@ -213,8 +213,8 @@ class BookmarkFilter
         $explodedSearchAnd = array_values(array_filter($explodedSearchAnd));
 
         // Filter excluding terms and update andSearch.
-        $excludeSearch = array();
-        $andSearch = array();
+        $excludeSearch = [];
+        $andSearch = [];
         foreach ($explodedSearchAnd as $needle) {
             if ($needle[0] == '-' && strlen($needle) > 1) {
                 $excludeSearch[] = substr($needle, 1);
@@ -234,33 +234,38 @@ class BookmarkFilter
                 }
             }
 
-            // Concatenate link fields to search across fields.
-            // Adds a '\' separator for exact search terms.
-            $content  = mb_convert_case($link->getTitle(), MB_CASE_LOWER, 'UTF-8') .'\\';
-            $content .= mb_convert_case($link->getDescription(), MB_CASE_LOWER, 'UTF-8') .'\\';
-            $content .= mb_convert_case($link->getUrl(), MB_CASE_LOWER, 'UTF-8') .'\\';
-            $content .= mb_convert_case($link->getTagsString(), MB_CASE_LOWER, 'UTF-8') .'\\';
+            $lengths = [];
+            $content = $this->buildFullTextSearchableLink($link, $lengths);
 
             // Be optimistic
             $found = true;
+            $foundPositions = [];
 
             // First, we look for exact term search
-            for ($i = 0; $i < count($exactSearch) && $found; $i++) {
-                $found = strpos($content, $exactSearch[$i]) !== false;
-            }
-
-            // Iterate over keywords, if keyword is not found,
+            // Then iterate over keywords, if keyword is not found,
             // no need to check for the others. We want all or nothing.
-            for ($i = 0; $i < count($andSearch) && $found; $i++) {
-                $found = strpos($content, $andSearch[$i]) !== false;
+            foreach ([$exactSearch, $andSearch] as $search) {
+                for ($i = 0; $i < count($search) && $found !== false; $i++) {
+                    $found = mb_strpos($content, $search[$i]);
+                    if ($found === false) {
+                        break;
+                    }
+
+                    $foundPositions[] = ['start' => $found, 'end' => $found + mb_strlen($search[$i])];
+                }
             }
 
             // Exclude terms.
-            for ($i = 0; $i < count($excludeSearch) && $found; $i++) {
+            for ($i = 0; $i < count($excludeSearch) && $found !== false; $i++) {
                 $found = strpos($content, $excludeSearch[$i]) === false;
             }
 
-            if ($found) {
+            if ($found !== false) {
+                $link->addAdditionalContentEntry(
+                    'search_highlight',
+                    $this->postProcessFoundPositions($lengths, $foundPositions)
+                );
+
                 $filtered[$id] = $link;
             }
         }
@@ -477,4 +482,74 @@ class BookmarkFilter
 
         return preg_split('/\s+/', $tagsOut, -1, PREG_SPLIT_NO_EMPTY);
     }
+
+    /**
+     * This method finalize the content of the foundPositions array,
+     * by associated all search results to their associated bookmark field,
+     * making sure that there is no overlapping results, etc.
+     *
+     * @param array $fieldLengths   Start and end positions of every bookmark fields in the aggregated bookmark content.
+     * @param array $foundPositions Positions where the search results were found in the aggregated content.
+     *
+     * @return array Updated $foundPositions, by bookmark field.
+     */
+    protected function postProcessFoundPositions(array $fieldLengths, array $foundPositions): array
+    {
+        // Sort results by starting position ASC.
+        usort($foundPositions, function (array $entryA, array $entryB): int {
+            return $entryA['start'] > $entryB['start'] ? 1 : -1;
+        });
+
+        $out = [];
+        $currentMax = -1;
+        foreach ($foundPositions as $foundPosition) {
+            // we do not allow overlapping highlights
+            if ($foundPosition['start'] < $currentMax) {
+                continue;
+            }
+
+            $currentMax = $foundPosition['end'];
+            foreach ($fieldLengths as $part => $length) {
+                if ($foundPosition['start'] < $length['start'] || $foundPosition['start'] > $length['end']) {
+                    continue;
+                }
+
+                $out[$part][] = [
+                    'start' => $foundPosition['start'] - $length['start'],
+                    'end' => $foundPosition['end'] - $length['start'],
+                ];
+                break;
+            }
+        }
+
+        return $out;
+    }
+
+    /**
+     * Concatenate link fields to search across fields. Adds a '\' separator for exact search terms.
+     * Also populate $length array with starting and ending positions of every bookmark field
+     * inside concatenated content.
+     *
+     * @param Bookmark $link
+     * @param array    $lengths (by reference)
+     *
+     * @return string Lowercase concatenated fields content.
+     */
+    protected function buildFullTextSearchableLink(Bookmark $link, array &$lengths): string
+    {
+        $content  = mb_convert_case($link->getTitle(), MB_CASE_LOWER, 'UTF-8') .'\\';
+        $content .= mb_convert_case($link->getDescription(), MB_CASE_LOWER, 'UTF-8') .'\\';
+        $content .= mb_convert_case($link->getUrl(), MB_CASE_LOWER, 'UTF-8') .'\\';
+        $content .= mb_convert_case($link->getTagsString(), MB_CASE_LOWER, 'UTF-8') .'\\';
+
+        $lengths['title'] = ['start' => 0, 'end' => mb_strlen($link->getTitle())];
+        $nextField = $lengths['title']['end'] + 1;
+        $lengths['description'] = ['start' => $nextField, 'end' => $nextField + mb_strlen($link->getDescription())];
+        $nextField = $lengths['description']['end'] + 1;
+        $lengths['url'] = ['start' => $nextField, 'end' => $nextField + mb_strlen($link->getUrl())];
+        $nextField = $lengths['url']['end'] + 1;
+        $lengths['tags'] = ['start' => $nextField, 'end' => $nextField + mb_strlen($link->getTagsString())];
+
+        return $content;
+    }
 }