Merge pull request #697 from ArthurHoaro/feature/ids-bis

Link ID refactoring

7 files changed, 232 insertions, 85 deletions

diff --git a/application/FeedBuilder.php b/application/FeedBuilder.php
index 4036a7cc..fedd90e6 100644
--- a/application/FeedBuilder.php
+++ b/application/FeedBuilder.php
@@ -143,7 +143,7 @@ class FeedBuilder
      */
     protected function buildItem($link, $pageaddr)
     {
-        $link['guid'] = $pageaddr .'?'. smallHash($link['linkdate']);
+        $link['guid'] = $pageaddr .'?'. $link['shorturl'];
         // Check for both signs of a note: starting with ? and 7 chars long.
         if ($link['url'][0] === '?' && strlen($link['url']) === 7) {
             $link['url'] = $pageaddr . $link['url'];
@@ -156,12 +156,12 @@ class FeedBuilder
         $link['description']  = format_description($link['description'], '', $pageaddr);
         $link['description'] .= PHP_EOL .'<br>&#8212; '. $permalink;
 
-        $pubDate = DateTime::createFromFormat(LinkDB::LINK_DATE_FORMAT, $link['linkdate']);
+        $pubDate = $link['created'];
         $link['pub_iso_date'] = $this->getIsoDate($pubDate);
 
         // atom:entry elements MUST contain exactly one atom:updated element.
         if (!empty($link['updated'])) {
-            $upDate = DateTime::createFromFormat(LinkDB::LINK_DATE_FORMAT, $link['updated']);
+            $upDate = $link['updated'];
             $link['up_iso_date'] = $this->getIsoDate($upDate, DateTime::ATOM);
         } else {
             $link['up_iso_date'] = $this->getIsoDate($pubDate, DateTime::ATOM);;
diff --git a/application/LinkDB.php b/application/LinkDB.php
index c8b162b6..1e13286a 100644
--- a/application/LinkDB.php
+++ b/application/LinkDB.php
@@ -6,15 +6,15 @@
  *
  * Example:
  *    $myLinks = new LinkDB();
- *    echo $myLinks['20110826_161819']['title'];
+ *    echo $myLinks[350]['title'];
  *    foreach ($myLinks as $link)
  *       echo $link['title'].' at url '.$link['url'].'; description:'.$link['description'];
  *
  * Available keys:
+ *  - id:       primary key, incremental integer identifier (persistent)
  *  - description: description of the entry
- *  - linkdate: creation date of this entry, format: YYYYMMDD_HHMMSS
- *              (e.g.'20110914_192317')
- *  - updated:  last modification date of this entry, format: YYYYMMDD_HHMMSS
+ *  - created:  creation date of this entry, DateTime object.
+ *  - updated:  last modification date of this entry, DateTime object.
  *  - private:  Is this link private? 0=no, other value=yes
  *  - tags:     tags attached to this entry (separated by spaces)
  *  - title     Title of the link
@@ -22,11 +22,25 @@
  *              Can be absolute or relative.
  *              Relative URLs are permalinks (e.g.'?m-ukcw')
  *  - real_url  Absolute processed URL.
+ *  - shorturl  Permalink smallhash
  *
  * Implements 3 interfaces:
  *  - ArrayAccess: behaves like an associative array;
  *  - Countable:   there is a count() method;
  *  - Iterator:    usable in foreach () loops.
+ *
+ * ID mechanism:
+ *   ArrayAccess is implemented in a way that will allow to access a link
+ *   with the unique identifier ID directly with $link[ID].
+ *   Note that it's not the real key of the link array attribute.
+ *   This mechanism is in place to have persistent link IDs,
+ *   even though the internal array is reordered by date.
+ *   Example:
+ *     - DB: link #1 (2010-01-01) link #2 (2016-01-01)
+ *     - Order: #2 #1
+ *     - Import links containing: link #3 (2013-01-01)
+ *     - New DB: link #1 (2010-01-01) link #2 (2016-01-01) link #3 (2013-01-01)
+ *     - Real order: #2 #3 #1
  */
 class LinkDB implements Iterator, Countable, ArrayAccess
 {
@@ -47,11 +61,17 @@ class LinkDB implements Iterator, Countable, ArrayAccess
     //  - value: associative array (keys: title, description...)
     private $links;
 
-    // List of all recorded URLs (key=url, value=linkdate)
-    // for fast reserve search (url-->linkdate)
+    // List of all recorded URLs (key=url, value=link offset)
+    // for fast reserve search (url-->link offset)
     private $urls;
 
-    // List of linkdate keys (for the Iterator interface implementation)
+    /**
+     * @var array List of all links IDS mapped with their array offset.
+     *            Map: id->offset.
+     */
+    protected $ids;
+
+    // List of offset keys (for the Iterator interface implementation)
     private $keys;
 
     // Position in the $this->keys array (for the Iterator interface)
@@ -121,14 +141,26 @@ class LinkDB implements Iterator, Countable, ArrayAccess
         if (!$this->loggedIn) {
             die('You are not authorized to add a link.');
         }
-        if (empty($value['linkdate']) || empty($value['url'])) {
-            die('Internal Error: A link should always have a linkdate and URL.');
+        if (!isset($value['id']) || empty($value['url'])) {
+            die('Internal Error: A link should always have an id and URL.');
         }
-        if (empty($offset)) {
-            die('You must specify a key.');
+        if ((! empty($offset) && ! is_int($offset)) || ! is_int($value['id'])) {
+            die('You must specify an integer as a key.');
+        }
+        if (! empty($offset) && $offset !== $value['id']) {
+            die('Array offset and link ID must be equal.');
+        }
+
+        // If the link exists, we reuse the real offset, otherwise new entry
+        $existing = $this->getLinkOffset($offset);
+        if ($existing !== null) {
+            $offset = $existing;
+        } else {
+            $offset = count($this->links);
         }
         $this->links[$offset] = $value;
-        $this->urls[$value['url']]=$offset;
+        $this->urls[$value['url']] = $offset;
+        $this->ids[$value['id']] = $offset;
     }
 
     /**
@@ -136,7 +168,7 @@ class LinkDB implements Iterator, Countable, ArrayAccess
      */
     public function offsetExists($offset)
     {
-        return array_key_exists($offset, $this->links);
+        return array_key_exists($this->getLinkOffset($offset), $this->links);
     }
 
     /**
@@ -148,9 +180,11 @@ class LinkDB implements Iterator, Countable, ArrayAccess
             // TODO: raise an exception
             die('You are not authorized to delete a link.');
         }
-        $url = $this->links[$offset]['url'];
+        $realOffset = $this->getLinkOffset($offset);
+        $url = $this->links[$realOffset]['url'];
         unset($this->urls[$url]);
-        unset($this->links[$offset]);
+        unset($this->ids[$realOffset]);
+        unset($this->links[$realOffset]);
     }
 
     /**
@@ -158,7 +192,8 @@ class LinkDB implements Iterator, Countable, ArrayAccess
      */
     public function offsetGet($offset)
     {
-        return isset($this->links[$offset]) ? $this->links[$offset] : null;
+        $realOffset = $this->getLinkOffset($offset);
+        return isset($this->links[$realOffset]) ? $this->links[$realOffset] : null;
     }
 
     /**
@@ -166,7 +201,7 @@ class LinkDB implements Iterator, Countable, ArrayAccess
      */
     public function current()
     {
-        return $this->links[$this->keys[$this->position]];
+        return $this[$this->keys[$this->position]];
     }
 
     /**
@@ -192,8 +227,7 @@ class LinkDB implements Iterator, Countable, ArrayAccess
      */
     public function rewind()
     {
-        $this->keys = array_keys($this->links);
-        rsort($this->keys);
+        $this->keys = array_keys($this->ids);
         $this->position = 0;
     }
 
@@ -219,6 +253,7 @@ class LinkDB implements Iterator, Countable, ArrayAccess
         // Create a dummy database for example
         $this->links = array();
         $link = array(
+            'id' => 1,
             'title'=>' Shaarli: the personal, minimalist, super-fast, no-database delicious clone',
             'url'=>'https://github.com/shaarli/Shaarli/wiki',
             'description'=>'Welcome to Shaarli! This is your first public bookmark. To edit or delete me, you must first login.
@@ -227,20 +262,23 @@ To learn how to use Shaarli, consult the link "Help/documentation" at the bottom
 
 You use the community supported version of the original Shaarli project, by Sebastien Sauvage.',
             'private'=>0,
-            'linkdate'=> date('Ymd_His'),
+            'created'=> new DateTime(),
             'tags'=>'opensource software'
         );
-        $this->links[$link['linkdate']] = $link;
+        $link['shorturl'] = link_small_hash($link['created'], $link['id']);
+        $this->links[1] = $link;
 
         $link = array(
+            'id' => 0,
             'title'=>'My secret stuff... - Pastebin.com',
             'url'=>'http://sebsauvage.net/paste/?8434b27936c09649#bR7XsXhoTiLcqCpQbmOpBi3rq2zzQUC5hBI7ZT1O3x8=',
             'description'=>'Shhhh! I\'m a private link only YOU can see. You can delete me too.',
             'private'=>1,
-            'linkdate'=> date('Ymd_His', strtotime('-1 minute')),
-            'tags'=>'secretstuff'
+            'created'=> new DateTime('1 minute ago'),
+            'tags'=>'secretstuff',
         );
-        $this->links[$link['linkdate']] = $link;
+        $link['shorturl'] = link_small_hash($link['created'], $link['id']);
+        $this->links[0] = $link;
 
         // Write database to disk
         $this->write();
@@ -251,7 +289,6 @@ You use the community supported version of the original Shaarli project, by Seba
      */
     private function read()
     {
-
         // Public links are hidden and user not logged in => nothing to show
         if ($this->hidePublicLinks && !$this->loggedIn) {
             $this->links = array();
@@ -269,23 +306,13 @@ You use the community supported version of the original Shaarli project, by Seba
                        strlen(self::$phpPrefix), -strlen(self::$phpSuffix)))));
         }
 
-        // If user is not logged in, filter private links.
-        if (!$this->loggedIn) {
-            $toremove = array();
-            foreach ($this->links as $link) {
-                if ($link['private'] != 0) {
-                    $toremove[] = $link['linkdate'];
-                }
-            }
-            foreach ($toremove as $linkdate) {
-                unset($this->links[$linkdate]);
+        $toremove = array();
+        foreach ($this->links as $key => &$link) {
+            if (! $this->loggedIn && $link['private'] != 0) {
+                // Transition for not upgraded databases.
+                $toremove[] = $key;
+                continue;
             }
-        }
-
-        $this->urls = array();
-        foreach ($this->links as &$link) {
-            // Keep the list of the mapping URLs-->linkdate up-to-date.
-            $this->urls[$link['url']] = $link['linkdate'];
 
             // Sanitize data fields.
             sanitizeLink($link);
@@ -307,7 +334,24 @@ You use the community supported version of the original Shaarli project, by Seba
             else {
                 $link['real_url'] = $link['url'];
             }
+
+            // To be able to load links before running the update, and prepare the update
+            if (! isset($link['created'])) {
+                $link['id'] = $link['linkdate'];
+                $link['created'] = DateTime::createFromFormat(self::LINK_DATE_FORMAT, $link['linkdate']);
+                if (! empty($link['updated'])) {
+                    $link['updated'] = DateTime::createFromFormat(self::LINK_DATE_FORMAT, $link['updated']);
+                }
+                $link['shorturl'] = smallHash($link['linkdate']);
+            }
+        }
+
+        // If user is not logged in, filter private links.
+        foreach ($toremove as $offset) {
+            unset($this->links[$offset]);
         }
+
+        $this->reorder();
     }
 
     /**
@@ -430,7 +474,7 @@ You use the community supported version of the original Shaarli project, by Seba
             $request = '';
         }
 
-        $linkFilter = new LinkFilter($this->links);
+        $linkFilter = new LinkFilter($this);
         return $linkFilter->filter($type, $request, $casesensitive, $privateonly);
     }
 
@@ -467,12 +511,64 @@ You use the community supported version of the original Shaarli project, by Seba
     public function days()
     {
         $linkDays = array();
-        foreach (array_keys($this->links) as $day) {
-            $linkDays[substr($day, 0, 8)] = 0;
+        foreach ($this->links as $link) {
+            $linkDays[$link['created']->format('Ymd')] = 0;
         }
         $linkDays = array_keys($linkDays);
         sort($linkDays);
 
         return $linkDays;
     }
+
+    /**
+     * Reorder links by creation date (newest first).
+     *
+     * Also update the urls and ids mapping arrays.
+     *
+     * @param string $order ASC|DESC
+     */
+    public function reorder($order = 'DESC')
+    {
+        $order = $order === 'ASC' ? -1 : 1;
+        // Reorder array by dates.
+        usort($this->links, function($a, $b) use ($order) {
+            return $a['created'] < $b['created'] ? 1 * $order : -1 * $order;
+        });
+
+        $this->urls = array();
+        $this->ids = array();
+        foreach ($this->links as $key => $link) {
+            $this->urls[$link['url']] = $key;
+            $this->ids[$link['id']] = $key;
+        }
+    }
+
+    /**
+     * Return the next key for link creation.
+     * E.g. If the last ID is 597, the next will be 598.
+     *
+     * @return int next ID.
+     */
+    public function getNextId()
+    {
+        if (!empty($this->ids)) {
+            return max(array_keys($this->ids)) + 1;
+        }
+        return 0;
+    }
+
+    /**
+     * Returns a link offset in links array from its unique ID.
+     *
+     * @param int $id Persistent ID of a link.
+     *
+     * @return int Real offset in local array, or null if doesn't exist.
+     */
+    protected function getLinkOffset($id)
+    {
+        if (isset($this->ids[$id])) {
+            return $this->ids[$id];
+        }
+        return null;
+    }
 }
diff --git a/application/LinkFilter.php b/application/LinkFilter.php
index d4fe28df..daa6d9cc 100644
--- a/application/LinkFilter.php
+++ b/application/LinkFilter.php
@@ -33,12 +33,12 @@ class LinkFilter
     public static $HASHTAG_CHARS = '\p{Pc}\p{N}\p{L}\p{Mn}';
 
     /**
-     * @var array all available links.
+     * @var LinkDB all available links.
      */
     private $links;
 
     /**
-     * @param array $links initialization.
+     * @param LinkDB $links initialization.
      */
     public function __construct($links)
     {
@@ -94,18 +94,16 @@ class LinkFilter
     private function noFilter($privateonly = false)
     {
         if (! $privateonly) {
-            krsort($this->links);
             return $this->links;
         }
 
         $out = array();
-        foreach ($this->links as $value) {
+        foreach ($this->links as $key => $value) {
             if ($value['private']) {
-                $out[$value['linkdate']] = $value;
+                $out[$key] = $value;
             }
         }
 
-        krsort($out);
         return $out;
     }
 
@@ -121,10 +119,10 @@ class LinkFilter
     private function filterSmallHash($smallHash)
     {
         $filtered = array();
-        foreach ($this->links as $l) {
-            if ($smallHash == smallHash($l['linkdate'])) {
+        foreach ($this->links as $key => $l) {
+            if ($smallHash == $l['shorturl']) {
                 // Yes, this is ugly and slow
-                $filtered[$l['linkdate']] = $l;
+                $filtered[$key] = $l;
                 return $filtered;
             }
         }
@@ -188,7 +186,7 @@ class LinkFilter
         $keys = array('title', 'description', 'url', 'tags');
 
         // Iterate over every stored link.
-        foreach ($this->links as $link) {
+        foreach ($this->links as $id => $link) {
 
             // ignore non private links when 'privatonly' is on.
             if (! $link['private'] && $privateonly === true) {
@@ -222,11 +220,10 @@ class LinkFilter
             }
 
             if ($found) {
-                $filtered[$link['linkdate']] = $link;
+                $filtered[$id] = $link;
             }
         }
 
-        krsort($filtered);
         return $filtered;
     }
 
@@ -256,7 +253,7 @@ class LinkFilter
             return $filtered;
         }
 
-        foreach ($this->links as $link) {
+        foreach ($this->links as $key => $link) {
             // ignore non private links when 'privatonly' is on.
             if (! $link['private'] && $privateonly === true) {
                 continue;
@@ -278,10 +275,9 @@ class LinkFilter
             }
 
             if ($found) {
-                $filtered[$link['linkdate']] = $link;
+                $filtered[$key] = $link;
             }
         }
-        krsort($filtered);
         return $filtered;
     }
 
@@ -304,13 +300,14 @@ class LinkFilter
         }
 
         $filtered = array();
-        foreach ($this->links as $l) {
-            if (startsWith($l['linkdate'], $day)) {
-                $filtered[$l['linkdate']] = $l;
+        foreach ($this->links as $key => $l) {
+            if ($l['created']->format('Ymd') == $day) {
+                $filtered[$key] = $l;
             }
         }
-        ksort($filtered);
-        return $filtered;
+
+        // sort by date ASC
+        return array_reverse($filtered, true);
     }
 
     /**
diff --git a/application/LinkUtils.php b/application/LinkUtils.php
index 9d9ae3cb..cf58f808 100644
--- a/application/LinkUtils.php
+++ b/application/LinkUtils.php
@@ -169,3 +169,16 @@ function space2nbsp($text)
 function format_description($description, $redirector = '', $indexUrl = '') {
     return nl2br(space2nbsp(hashtag_autolink(text2clickable($description, $redirector), $indexUrl)));
 }
+
+/**
+ * Generate a small hash for a link.
+ *
+ * @param DateTime $date Link creation date.
+ * @param int      $id   Link ID.
+ *
+ * @return string the small hash generated from link data.
+ */
+function link_small_hash($date, $id)
+{
+    return smallHash($date->format(LinkDB::LINK_DATE_FORMAT) . $id);
+}
diff --git a/application/NetscapeBookmarkUtils.php b/application/NetscapeBookmarkUtils.php
index dd21f05b..e7148d00 100644
--- a/application/NetscapeBookmarkUtils.php
+++ b/application/NetscapeBookmarkUtils.php
@@ -38,7 +38,7 @@ class NetscapeBookmarkUtils
             if ($link['private'] == 0 && $selection == 'private') {
                 continue;
             }
-            $date = DateTime::createFromFormat(LinkDB::LINK_DATE_FORMAT, $link['linkdate']);
+            $date = $link['created'];
             $link['timestamp'] = $date->getTimestamp();
             $link['taglist'] = str_replace(' ', ',', $link['tags']);
 
@@ -147,7 +147,6 @@ class NetscapeBookmarkUtils
                 'url' => $bkm['uri'],
                 'description' => $bkm['note'],
                 'private' => $private,
-                'linkdate'=> '',
                 'tags' => $bkm['tags']
             );
 
@@ -161,25 +160,22 @@ class NetscapeBookmarkUtils
                 }
 
                 // Overwrite an existing link, keep its date
-                $newLink['linkdate'] = $existingLink['linkdate'];
-                $linkDb[$existingLink['linkdate']] = $newLink;
+                $newLink['id'] = $existingLink['id'];
+                $newLink['created'] = $existingLink['created'];
+                $newLink['updated'] = new DateTime();
+                $linkDb[$existingLink['id']] = $newLink;
                 $importCount++;
                 $overwriteCount++;
                 continue;
             }
 
-            // Add a new link
+            // Add a new link - @ used for UNIX timestamps
             $newLinkDate = new DateTime('@'.strval($bkm['time']));
-            while (!empty($linkDb[$newLinkDate->format(LinkDB::LINK_DATE_FORMAT)])) {
-                // Ensure the date/time is not already used
-                // - this hack is necessary as the date/time acts as a primary key
-                // - apply 1 second increments until an unused index is found
-                // See https://github.com/shaarli/Shaarli/issues/351
-                $newLinkDate->add(new DateInterval('PT1S'));
-            }
-            $linkDbDate = $newLinkDate->format(LinkDB::LINK_DATE_FORMAT);
-            $newLink['linkdate'] = $linkDbDate;
-            $linkDb[$linkDbDate] = $newLink;
+            $newLinkDate->setTimezone(new DateTimeZone(date_default_timezone_get()));
+            $newLink['created'] = $newLinkDate;
+            $newLink['id'] = $linkDb->getNextId();
+            $newLink['shorturl'] = link_small_hash($newLink['created'], $newLink['id']);
+            $linkDb[$newLink['id']] = $newLink;
             $importCount++;
         }
 
diff --git a/application/Updater.php b/application/Updater.php
index 36eddd4f..f0d02814 100644
--- a/application/Updater.php
+++ b/application/Updater.php
@@ -138,10 +138,10 @@ class Updater
     public function updateMethodRenameDashTags()
     {
         $linklist = $this->linkDB->filterSearch();
-        foreach ($linklist as $link) {
+        foreach ($linklist as $key => $link) {
             $link['tags'] = preg_replace('/(^| )\-/', '$1', $link['tags']);
             $link['tags'] = implode(' ', array_unique(LinkFilter::tagsStrToArray($link['tags'], true)));
-            $this->linkDB[$link['linkdate']] = $link;
+            $this->linkDB[$key] = $link;
         }
         $this->linkDB->save($this->conf->get('resource.page_cache'));
         return true;
@@ -215,6 +215,47 @@ class Updater
         }
         return true;
     }
+
+    /**
+     * Update the database to use the new ID system, which replaces linkdate primary keys.
+     * Also, creation and update dates are now DateTime objects (done by LinkDB).
+     *
+     * Since this update is very sensitve (changing the whole database), the datastore will be
+     * automatically backed up into the file datastore.<datetime>.php.
+     *
+     * LinkDB also adds the field 'shorturl' with the precedent format (linkdate smallhash),
+     * which will be saved by this method.
+     *
+     * @return bool true if the update is successful, false otherwise.
+     */
+    public function updateMethodDatastoreIds()
+    {
+        // up to date database
+        if (isset($this->linkDB[0])) {
+            return true;
+        }
+
+        $save = $this->conf->get('resource.data_dir') .'/datastore.'. date('YmdHis') .'.php';
+        copy($this->conf->get('resource.datastore'), $save);
+
+        $links = array();
+        foreach ($this->linkDB as $offset => $value) {
+            $links[] = $value;
+            unset($this->linkDB[$offset]);
+        }
+        $links = array_reverse($links);
+        $cpt = 0;
+        foreach ($links as $l) {
+            unset($l['linkdate']);
+            $l['id'] = $cpt;
+            $this->linkDB[$cpt++] = $l;
+        }
+
+        $this->linkDB->save($this->conf->get('resource.page_cache'));
+        $this->linkDB->reorder();
+
+        return true;
+    }
 }
 
 /**
diff --git a/application/Utils.php b/application/Utils.php
index 0166ee2a..0a5b476e 100644
--- a/application/Utils.php
+++ b/application/Utils.php
@@ -31,7 +31,11 @@ function logm($logFile, $clientIp, $message)
  *   - are NOT cryptographically secure (they CAN be forged)
  *
  *  In Shaarli, they are used as a tinyurl-like link to individual entries,
- *  e.g. smallHash('20111006_131924') --> yZH23w
+ *  built once with the combination of the date and item ID.
+ *  e.g. smallHash('20111006_131924' . 142) --> eaWxtQ
+ *
+ * @warning before v0.8.1, smallhashes were built only with the date,
+ *          and their value has been preserved.
  *
  * @param string $text Create a hash from this text.
  *