Bug 1039200 Part 2 - Add implementation of new tagging API with unit tests, r?mak draft
authorMilindL <i.milind.luthra@gmail.com>
Tue, 11 Jul 2017 11:18:19 +0530
changeset 607526 3d3057faa23339f5933da73d14aea84729a3c465
parent 607279 cd5798c8ec86b93616e1a6fecf0f65e52661a722
child 637050 0a6ae0716cbfba066343fccc9184425e855612e9
push id68007
push userbmo:i.milind.luthra@gmail.com
push dateWed, 12 Jul 2017 10:09:47 +0000
reviewersmak
bugs1039200
milestone56.0a1
Bug 1039200 Part 2 - Add implementation of new tagging API with unit tests, r?mak This change adds several new API and changes the current API to add tagging functionality to Bookmarks.jsm. The following API are added (with a brief overview of their function): 1. Insert({..addTags:[]}) This will add these tags along with the bookmark it is inserting. If the tag doesn't exist in the moz_tags database, it is added there. If the tag has a different case in moz_tags database, it is updated there. 2. InsertTree(...) The `tags` property on the various children is read and tag-url relations are made. Tags are added/replaced as in 1. if they don't exist/case is different. 3. Update({...addTags:[], removeTags:[]}) This will add and remove the tags specified in these arrays to the bookmark. This will also update the tags-url relations when the `url` property is specified in the update information. This will remove tags from moz_tables which do not have any url association. 4. Remove() If any bookmark is removed, this method removes all tags associated with it, as long as the url does not have another bookmark associated with it. Any folder removal is also handled similarly in terms of bookmarks inside them. This will remove tags from moz_tables which do not have any url association. 5. Fetch(tags: []) By specifying a tags array, bookmarks can be fetched which are tagged with all the specified tags. 6. FetchTags(guidOrUrlOrNothing) This will fetch all tags or tags for a bookmark guid or a url. Note that internally, it uses urls, becase of the tag-url schema. MozReview-Commit-ID: 18cHNjHee43
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/PlacesUtils.jsm
toolkit/components/places/tests/bookmarks/test_bookmarks_fetch.js
toolkit/components/places/tests/bookmarks/test_bookmarks_fetchTags.js
toolkit/components/places/tests/bookmarks/test_bookmarks_insert.js
toolkit/components/places/tests/bookmarks/test_bookmarks_insertTree.js
toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
toolkit/components/places/tests/bookmarks/test_bookmarks_removeTagsIfEmpty.js
toolkit/components/places/tests/bookmarks/test_bookmarks_update.js
toolkit/components/places/tests/bookmarks/xpcshell.ini
toolkit/components/places/tests/head_common.js
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -89,16 +89,30 @@ async function promiseTagsFolderId() {
   let db =  await PlacesUtils.promiseDBConnection();
   let rows = await db.execute(
     "SELECT id FROM moz_bookmarks WHERE guid = :guid",
     { guid: Bookmarks.tagsGuid }
   );
   return gTagsFolderId = rows[0].getResultByName("id");
 }
 
+XPCOMUtils.defineLazyGetter(
+  this, "gTagsCachePromise",
+  () => PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: gTagsCachePromise",
+    async (db) => {
+      let rows = await db.executeCached(`SELECT id, tag FROM moz_tags`);
+      const cache = new Map();
+      for (let row of rows) {
+        cache.set(row.getResultByName("tag"), parseInt(row.getResultByName("id")));
+      }
+      return cache;
+    })
+);
+
 const MATCH_ANYWHERE_UNMODIFIED = Ci.mozIPlacesAutoComplete.MATCH_ANYWHERE_UNMODIFIED;
 const BEHAVIOR_BOOKMARK = Ci.mozIPlacesAutoComplete.BEHAVIOR_BOOKMARK;
 
 var Bookmarks = Object.freeze({
   /**
    * Item's type constants.
    * These should stay consistent with nsINavBookmarksService.idl
    */
@@ -165,16 +179,20 @@ var Bookmarks = Object.freeze({
    * If an index is not specified, it defaults to appending.
    * It's also possible to pass a non-existent GUID to force creation of an
    * item with the given GUID, but unless you have a very sound reason, such as
    * an undo manager implementation or synchronization, don't do that.
    *
    * Note that any known properties that don't apply to the specific item type
    * cause an exception.
    *
+   * Note that an additional array of strings, `addTags` can be specified as a part
+   * of the info object. The bookmark is tagged with these tags. This array is not a
+   * part of the returned bookmark object.
+   *
    * @param info
    *        object representing a bookmark-item.
    *
    * @return {Promise} resolved when the creation is complete.
    * @resolves to an object representing the created bookmark.
    * @rejects if it's not possible to create the requested bookmark.
    * @throws if the arguments are invalid.
    */
@@ -191,32 +209,37 @@ var Bookmarks = Object.freeze({
         url: { requiredIf: b => b.type == this.TYPE_BOOKMARK,
                validIf: b => b.type == this.TYPE_BOOKMARK },
         parentGuid: { required: true },
         title: { validIf: b => [ this.TYPE_BOOKMARK,
                                  this.TYPE_FOLDER ].includes(b.type) },
         dateAdded: { defaultValue: addedTime },
         lastModified: { defaultValue: modTime,
                         validIf: b => b.lastModified >= now || (b.dateAdded && b.lastModified >= b.dateAdded) },
-        source: { defaultValue: this.SOURCES.DEFAULT }
+        source: { defaultValue: this.SOURCES.DEFAULT },
+        addTags: { defaultValue: [],
+                  validIf: b => b.type === this.TYPE_BOOKMARK }
       });
 
     return (async () => {
       // Ensure the parent exists.
       let parent = await fetchBookmark({ guid: insertInfo.parentGuid });
       if (!parent)
         throw new Error("parentGuid must be valid");
 
       // Set index in the appending case.
       if (insertInfo.index == this.DEFAULT_INDEX ||
           insertInfo.index > parent._childCount) {
         insertInfo.index = parent._childCount;
       }
 
       let item = await insertBookmark(insertInfo, parent);
+      if (item.type === this.TYPE_BOOKMARK) {
+        await addTagsForBookmark(item, insertInfo.addTags);
+      }
 
       // Notify onItemAdded to listeners.
       let observers = PlacesUtils.bookmarks.getObservers();
       // We need the itemId to notify, though once the switch to guids is
       // complete we may stop using it.
       let uri = item.hasOwnProperty("url") ? PlacesUtils.toURI(item.url) : null;
       let itemId = await PlacesUtils.promiseItemId(item.guid);
 
@@ -235,16 +258,19 @@ var Bookmarks = Object.freeze({
           notify(observers, "onItemChanged", [ entry._id, "tags", false, "",
                                                PlacesUtils.toPRTime(entry.lastModified),
                                                entry.type, entry._parentId,
                                                entry.guid, entry.parentGuid,
                                                "", item.source ]);
         }
       }
 
+      // Strip tagging properties from bookmark.
+      delete item.addTags;
+
       // Remove non-enumerable properties.
       delete item.source;
       return Object.assign({}, item);
     })();
   },
 
 
   /**
@@ -490,16 +516,18 @@ var Bookmarks = Object.freeze({
 
   /**
    * Updates a bookmark-item.
    *
    * Only set the properties which should be changed (undefined properties
    * won't be taken into account).
    * Moreover, the item's type or dateAdded cannot be changed, since they are
    * immutable after creation.  Trying to change them will reject.
+   * Tags to added and removed should be supplied as an array of strings `addTags`
+   * and `removeTags`. The final object returned has these properties stripped.
    *
    * Note that any known properties that don't apply to the specific item type
    * cause an exception.
    *
    * @param info
    *        object representing a bookmark-item, as defined above.
    *
    * @return {Promise} resolved when the update is complete.
@@ -510,33 +538,51 @@ var Bookmarks = Object.freeze({
   update(info) {
     // The info object is first validated here to ensure it's consistent, then
     // it's compared to the existing item to remove any properties that don't
     // need to be updated.
     let updateInfo = validateBookmarkObject(info,
       { guid: { required: true },
         index: { requiredIf: b => b.hasOwnProperty("parentGuid"),
                  validIf: b => b.index >= 0 || b.index == this.DEFAULT_INDEX },
-        source: { defaultValue: this.SOURCES.DEFAULT }
+        source: { defaultValue: this.SOURCES.DEFAULT },
+        addTags: { defaultValue: [],
+                   validIf: b => b.type = this.TYPE_BOOKMARK },
+        removeTags: { defaultValue: [],
+                      validIf: b => b.type = this.TYPE_BOOKMARK }
       });
 
+
+    let propertiesToUpdate = Object.keys(updateInfo).length;
+    // The number should not include add/removeTags if the length is zero.
+    propertiesToUpdate -= updateInfo.addTags.length ? 0 : 1;
+    propertiesToUpdate -= updateInfo.removeTags.length ? 0 : 1;
     // There should be at last one more property in addition to guid and source.
-    if (Object.keys(updateInfo).length < 3)
+    if (propertiesToUpdate < 3)
       throw new Error("Not enough properties to update");
 
     return (async () => {
       // Ensure the item exists.
       let item = await fetchBookmark(updateInfo);
       if (!item)
         throw new Error("No bookmarks found for the provided GUID");
       if (updateInfo.hasOwnProperty("type") && updateInfo.type != item.type)
         throw new Error("The bookmark type cannot be changed");
 
+      if (item.type !== this.TYPE_BOOKMARK) {
+        delete updateInfo.addTags;
+        delete updateInfo.removeTags;
+      }
+
       // Remove any property that will stay the same.
       removeSameValueProperties(updateInfo, item);
+      if (item.type === this.TYPE_BOOKMARK) {
+        await stripUnchangeableTags(updateInfo);
+      }
+
       // Check if anything should still be updated.
       if (Object.keys(updateInfo).length < 3) {
         // Remove non-enumerable properties.
         return Object.assign({}, item);
       }
       const now = new Date();
       let lastModifiedDefault = now;
       // In the case where `dateAdded` is specified, but `lastModified` is not,
@@ -550,18 +596,17 @@ var Bookmarks = Object.freeze({
           title: { validIf: () => [ this.TYPE_BOOKMARK,
                                     this.TYPE_FOLDER ].includes(item.type) },
           lastModified: { defaultValue: lastModifiedDefault,
                           validIf: b => b.lastModified >= now ||
                                         b.lastModified >= (b.dateAdded || item.dateAdded) },
           dateAdded: { defaultValue: item.dateAdded }
         });
 
-      return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: update",
-        async db => {
+      return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: update", async db => {
         let parent;
         if (updateInfo.hasOwnProperty("parentGuid")) {
           if (item.type == this.TYPE_FOLDER) {
             // Make sure we are not moving a folder into itself or one of its
             // descendants.
             let rows = await db.executeCached(
               `WITH RECURSIVE
                descendants(did) AS (
@@ -594,18 +639,53 @@ var Bookmarks = Object.freeze({
              updateInfo.index = parent._childCount;
 
             // Fix the index when moving within the same container.
             if (parent.guid == item.parentGuid)
                updateInfo.index--;
           }
         }
 
+        // Since tags are associated with URLs, a change in URL can cause us to deal with
+        // multiple cases. If URL changes from url1 -> url2, we need to remove all
+        // tag-url1 associations, but only if there are no other bookmarks with the same url1.
+        // Similarly, if there is a pre-existing bookmark with url2, we need to keep its
+        // existing tag-url2 associations as well as adding new ones.
+        // So, there are 4 cases to deal with (2 alternatives each for url1, url2).
+        let oldTags;
+        if (updateInfo.hasOwnProperty("url")) {
+          oldTags = await this.fetchTags({ url: item.url });
+          let multipleBookmarks = await checkMultipleBookmarks(item.url);
+          if (!multipleBookmarks) {
+            await removeTagsForBookmark(item);
+          }
+        }
         let updatedItem = await updateBookmark(updateInfo, item, parent);
 
+        if (updatedItem.type === this.TYPE_BOOKMARK) {
+          let addTags = updateInfo.addTags;
+          let removeTags = updateInfo.removeTags;
+          if (updateInfo.hasOwnProperty("url")) {
+            let multipleBookmarks = await checkMultipleBookmarks(updatedItem.url);
+            // Since the url is already changing, we can simply add
+            // oldTags + addTags - removeTags instead of adding those tags which will
+            // be removed later anyway. Note that a remove operation will still be performed,
+            // since url2 might have some preexisting tags.
+            addTags = oldTags.concat(updateInfo.addTags)
+                             .filter(t => !updateInfo.removeTags.includes(t));
+            if (!multipleBookmarks) {
+              // No need to remove any tags if url2 doesn't exist, we have already filtered them.
+              removeTags = [];
+            }
+          }
+          await addTagsForBookmark(updatedItem, addTags);
+          await removeTagsForBookmark(updatedItem, removeTags);
+        }
+
+
         if (item.type == this.TYPE_BOOKMARK &&
             item.url.href != updatedItem.url.href) {
           // ...though we don't wait for the calculation.
           updateFrecency(db, [item.url]).catch(Cu.reportError);
           updateFrecency(db, [updatedItem.url]).catch(Cu.reportError);
         }
 
         // Notify onItemChanged to listeners.
@@ -665,16 +745,19 @@ var Bookmarks = Object.freeze({
           notify(observers, "onItemMoved", [ updatedItem._id, item._parentId,
                                              item.index, updatedItem._parentId,
                                              updatedItem.index, updatedItem.type,
                                              updatedItem.guid, item.parentGuid,
                                              updatedItem.parentGuid,
                                              updatedItem.source ]);
         }
 
+        // Strip tagging properties.
+        delete updatedItem.addTags;
+        delete updatedItem.removeTags;
         // Remove non-enumerable properties.
         delete updatedItem.source;
         return Object.assign({}, updatedItem);
       });
     })();
   },
 
   /**
@@ -717,18 +800,28 @@ var Bookmarks = Object.freeze({
     // known property to reduce likelihood of hidden bugs.
     let removeInfo = validateBookmarkObject(info);
 
     return (async function() {
       let item = await fetchBookmark(removeInfo);
       if (!item)
         throw new Error("No bookmarks found for the provided GUID.");
 
+      // We need to clean up tag-place relations if another bookmark with the same
+      // url does not exist.
+      let multipleBookmarks = (item.type === PlacesUtils.bookmarks.TYPE_BOOKMARK) &&
+                              (await checkMultipleBookmarks(item.url));
+
       item = await removeBookmark(item, options);
 
+      if (item.type === PlacesUtils.bookmarks.TYPE_BOOKMARK &&
+          !multipleBookmarks) {
+        await removeTagsForBookmark(item);
+      }
+
       // Notify onItemRemoved to listeners.
       let observers = PlacesUtils.bookmarks.getObservers();
       let uri = item.hasOwnProperty("url") ? PlacesUtils.toURI(item.url) : null;
       let isUntagging = item._grandParentId == PlacesUtils.tagsFolderId;
       notify(observers, "onItemRemoved", [ item._id, item._parentId, item.index,
                                            item.type, uri, item.guid,
                                            item.parentGuid,
                                            options.source ],
@@ -833,16 +926,20 @@ var Bookmarks = Object.freeze({
    *  - guid
    *      retrieves the item with the specified guid.
    *  - parentGuid and index
    *      retrieves the item by its position.
    *  - url
    *      retrieves the most recent bookmark having the given URL.
    *      To retrieve ALL of the bookmarks for that URL, you must pass in an
    *      onResult callback, that will be invoked once for each found bookmark.
+   * - tags
+   *      retrieves a bookmark which is tagged with all the tags contained
+   *      inside this array. To retrieve all the bookmarks for a set of tags, a
+   *      callback must be passed, which will be invoked once per bookmark.
    *
    * @param guidOrInfo
    *        The globally unique identifier of the item to fetch, or an
    *        object representing it, as defined above.
    * @param onResult [optional]
    *        Callback invoked for each found bookmark.
    * @param options [optional]
    *        an optional object whose properties describe options for the fetch:
@@ -868,24 +965,25 @@ var Bookmarks = Object.freeze({
       throw new Error("onResult callback must be a valid function");
     let info = guidOrInfo;
     if (!info)
       throw new Error("Input should be a valid object");
     if (typeof(info) != "object") {
       info = { guid: guidOrInfo };
     } else if (Object.keys(info).length == 1) {
       // Just a faster code path.
-      if (!["url", "guid", "parentGuid", "index"].includes(Object.keys(info)[0]))
+      if (!["url", "guid", "parentGuid", "index", "tags"].includes(Object.keys(info)[0]))
         throw new Error(`Unexpected number of conditions provided: 0`);
     } else {
       // Only one condition at a time can be provided.
       let conditionsCount = [
         v => v.hasOwnProperty("guid"),
         v => v.hasOwnProperty("parentGuid") && v.hasOwnProperty("index"),
-        v => v.hasOwnProperty("url")
+        v => v.hasOwnProperty("url"),
+        v => v.hasOwnProperty("tags")
       ].reduce((old, fn) => old + fn(info) | 0, 0);
       if (conditionsCount != 1)
         throw new Error(`Unexpected number of conditions provided: ${conditionsCount}`);
     }
 
     let behavior = {};
     if (info.hasOwnProperty("parentGuid") || info.hasOwnProperty("index")) {
       behavior = {
@@ -903,43 +1001,129 @@ var Bookmarks = Object.freeze({
     return (async function() {
       let results;
       if (fetchInfo.hasOwnProperty("url"))
         results = await fetchBookmarksByURL(fetchInfo, options && options.concurrent);
       else if (fetchInfo.hasOwnProperty("guid"))
         results = await fetchBookmark(fetchInfo, options && options.concurrent);
       else if (fetchInfo.hasOwnProperty("parentGuid") && fetchInfo.hasOwnProperty("index"))
         results = await fetchBookmarkByPosition(fetchInfo, options && options.concurrent);
+      else if (fetchInfo.hasOwnProperty("tags"))
+        results = await fetchBookmarksByTags(fetchInfo, options && options.concurrent, onResult);
 
       if (!results)
         return null;
 
       if (!Array.isArray(results))
         results = [results];
       // Remove non-enumerable properties.
       results = results.map(r => Object.assign({}, r));
 
       // Ideally this should handle an incremental behavior and thus be invoked
       // while we fetch.  Though, the likelihood of 2 or more bookmarks for the
       // same match is very low, so it's not worth the added code complication.
-      if (onResult) {
+      // This does not hold true for fetching by tags, so we callback as we fetch.
+      if (onResult && !fetchInfo.hasOwnProperty("tags")) {
         for (let result of results) {
           try {
             onResult(result);
           } catch (ex) {
             Cu.reportError(ex);
           }
         }
       }
 
       return results[0];
     })();
   },
 
   /**
+     * Fetches a list of tags for given guid or URL. If nothing is is
+     * specified, fetches all tags. Note that the guid or URL must belong
+     * to a valid bookmark.
+     *
+     * @param guidOrUrlOrNothing [optional]
+     *        The globally unique identifier, `null` (default), or an
+     *        object with exactly one of these properties set:
+     *       - guid
+     *           retrieves the tags for the bookmark with the specified guid.
+     *       - url
+     *           retrieves the tags for the specified URL.
+     * @param onResult [optional]
+     *        A callback invoked for each tag in the list.
+     * @param options [optional]
+     *        An optional object containing the any of the following properties:
+     *        - concurrent: if true, tags are fetched concurrent to writes. This
+     *                      returns results faster at the cost of returning stale
+     *                      results missing the currently ongoing write. This does
+     *                      not apply to the call for all tags, which fetched non-
+     *                      concurrently initially, then cached.
+     *
+     * @return {Promise} resolved when the fetch is complete.
+     * @resolves to a sorted array of tags.
+     * @rejects if an error happens while fetching or if guid or URL is not bookmarked.
+     * @throws if the arguments are invalid.
+   */
+  fetchTags(guidOrUrlOrNothing = null, onResult = null, options = {}) {
+    if (!("concurrent" in options)) {
+      options.concurrent = false;
+    }
+
+    if (onResult && typeof onResult !== "function") {
+      throw new Error("onResult callback must be a valid function.");
+    }
+
+    // Verify that guidOrUrlOrNothing is ok.
+    if (typeof guidOrUrlOrNothing === "string") {
+      guidOrUrlOrNothing = { guid: guidOrUrlOrNothing };
+    }
+
+    if (guidOrUrlOrNothing != null) {
+      if (typeof guidOrUrlOrNothing !== "object") {
+        throw new Error("Input should be a valid object if not null");
+      }
+
+      let conditionsCount = [
+        v => v.hasOwnProperty("guid") ? 1 : 0,
+        v => v.hasOwnProperty("url") ? 1 : 0
+      ].reduce((old, fn) => old + fn(guidOrUrlOrNothing), 0);
+
+      if (conditionsCount !== 1) {
+        throw new Error(`Unexpected number of conditions provided: ${ conditionsCount }`);
+      }
+    }
+
+    return (async () => {
+      let tagsArray;
+      if (guidOrUrlOrNothing == null) {
+        const tagCache = await gTagsCachePromise;
+        tagsArray = Array.from(tagCache.keys()).sort();
+      } else {
+        // The given GUID or URL must already be a bookmark.
+        let bookmark = await this.fetch(guidOrUrlOrNothing, null, options);
+        if (bookmark === null || bookmark.type !== this.TYPE_BOOKMARK) {
+          throw new Error("The URL/GUID should point to a pre-existing bookmark");
+        }
+        tagsArray = await fetchTags(guidOrUrlOrNothing, options && options.concurrent);
+      }
+
+      if (onResult) {
+        for (let tag of tagsArray) {
+          try {
+            onResult(tag);
+          } catch (ex) {
+            Cu.reportError(ex);
+          }
+        }
+      }
+
+      return tagsArray.sort();
+    })();
+  },
+  /**
    * Retrieves an object representation of a bookmark-item, along with all of
    * its descendants, if any.
    *
    * Each node in the tree is an object that extends the item representation
    * described above with some additional properties:
    *
    *  - [deprecated] id (number)
    *      the item's id.  Defined only if aOptions.includeItemIds is set.
@@ -1140,16 +1324,133 @@ function notify(observers, notification,
     }
 
     try {
       observer[notification](...args);
     } catch (ex) {}
   }
 }
 
+// Add tags to bookmarks implementation.
+// Note that the item is a bookmark.
+async function addTagsForBookmark(item, tags) {
+  // Any tags that do not match the current list of tags are created/updated.
+  const tagsCache = await gTagsCachePromise;
+  for (let tag of tags) {
+    let matchingTags = Array.from(tagsCache.keys())
+                            .filter(aTag => aTag.toLowerCase() === tag.toLowerCase());
+    if (matchingTags.length === 0) {
+      // The tag doesn't exist, we need to create a tag.
+      let tagId = await maybeInsertTag(tag);
+      tagsCache.set(tag, tagId);
+    } else if (matchingTags[0] !== tag) {
+        // The tag exists, but we need to update the case.
+        await replaceTag(matchingTags[0], tag);
+        tagsCache.set(tag, tagsCache.get(matchingTags[0]));
+        tagsCache.delete(matchingTags[0]);
+    }
+
+    await PlacesUtils.withConnectionWrapper(
+      "Bookmarks.jsm: addTagsForBookmark",
+      async (db) => {
+        await db.executeCached(
+          `INSERT OR IGNORE INTO moz_tags_relation (tag_id, place_id)
+           SELECT :tag_id, h.id FROM moz_places h
+           WHERE h.url_hash = hash(:url) AND h.url = :url`,
+          {
+            tag_id: tagsCache.get(tag),
+            url: item.url.href
+          });
+      }
+    );
+  }
+}
+
+// Remove tags from bookmark (ie from a place).
+// Note that item can be anything with a property "url".
+// If `tags` are not specified, this deletes all tags.
+async function removeTagsForBookmark(item, tags = null) {
+  let tagIdFragment = "";
+  if (tags) {
+    const tagsCache = await gTagsCachePromise;
+    // We cannot remove any tags that do not exist, so filter.
+    let tagIdList = tags.filter(t => tagsCache.has(t))
+                        .map(t => tagsCache.get(t));
+    if (tagIdList.length === 0) {
+      // Quit early if none of the tags are existent.
+      return true;
+    }
+    let tagIdSqlList = "(" + tagIdList.join(", ") + ")";
+    tagIdFragment = `AND tag_id IN ${ tagIdSqlList }`;
+  }
+  return PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: removeTagsForBookmark",
+    async (db) => {
+      await db.executeCached(
+        `DELETE FROM moz_tags_relation
+         WHERE place_id = (SELECT id FROM moz_places h
+                           WHERE h.url_hash = hash(:url) AND h.url = :url)
+         ${ tagIdFragment }`,
+        { url: item.url.href });
+    }).then(() => {
+      // Each time we remove tags, we need to check if moz_tags is affected.
+      return removeTagsIfEmpty(tags);
+    });
+}
+
+/**
+ * Removes any tag inside the tags array if no entry exists in the
+ * moz_tags_relation table. This also updates the internal tags cache.
+ * @param tags [optional]
+ *        List of tags to check and remove if needed.
+ *        Defaults to checking all tags.
+ * @return {Promise} resolved when deletion is complete.
+ */
+async function removeTagsIfEmpty(tags = null) {
+  const tagsCache = await gTagsCachePromise;
+  let tagIdList;
+  let tagIdListFragment = "";
+  if (tags) {
+    tagIdList = tags.filter(t => tagsCache.has(t))
+                    .map(t => tagsCache.get(t));
+    tagIdListFragment = `AND id IN (${ tagIdList.join(", ") })`;
+  }
+
+  if (tagIdList && tagIdList.length === 0) {
+    // No tags to check and remove.
+    return;
+  }
+
+  let tagsToRemove = [];
+  await PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: removeTagsIfEmpty",
+    async (db) => {
+      await db.executeCached(
+        `SELECT id, tag FROM moz_tags
+         WHERE NOT EXISTS (SELECT 1 FROM moz_tags_relation WHERE tag_id = id)
+         ${ tagIdListFragment }`,
+        null,
+        row => {
+          tagsToRemove.push(row.getResultByName("id"));
+          tagsCache.delete(row.getResultByName("tag"));
+        }
+      );
+    });
+
+  let tagIdSqlList = "(" + tagsToRemove.join(", ") + ")";
+  await PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: removeTagsIfEmpty",
+    async (db) => {
+      await db.executeCached(
+        `DELETE FROM moz_tags
+         WHERE id IN ${ tagIdSqlList }`
+      );
+    });
+}
+
 // Update implementation.
 
 function updateBookmark(info, item, newParent) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
     async function(db) {
 
     let tuples = new Map();
     tuples.set("lastModified", { value: PlacesUtils.toPRTime(info.lastModified) });
@@ -1514,16 +1815,17 @@ async function handleBookmarkItemSpecial
         source: item.source
       });
     } catch (ex) {
       Cu.reportError(`Failed to insert keywords: ${ex}`);
     }
   }
   if ("tags" in item) {
     try {
+      await PlacesUtils.bookmarks.update(Object.assign(item, { addTags: item.tags }));
       PlacesUtils.tagging.tagURI(NetUtil.newURI(item.url), item.tags, item._source);
     } catch (ex) {
       // Invalid tag child, skip it.
       Cu.reportError(`Unable to set tags "${item.tags.join(", ")}" for ${item.url}: ${ex}`);
     }
   }
   if ("charset" in item && item.charset) {
     await PlacesUtils.setCharsetForURI(NetUtil.newURI(item.url), item.charset);
@@ -1663,16 +1965,71 @@ async function fetchBookmarksByURL(info,
   if (concurrent) {
     let db = await PlacesUtils.promiseDBConnection();
     return query(db);
   }
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchBookmarksByURL",
                                            query);
 }
 
+async function fetchBookmarksByTags(info, concurrent, onResult) {
+  const tagsCache = await gTagsCachePromise;
+
+  if (info.tags.some(t => !tagsCache.has(t))) {
+    // A tag is not in moz_tags, so there is no need to make a query.
+    return null;
+  }
+  let returnRow = null;
+  const tagsFolderId = await promiseTagsFolderId();
+  let tagSqlList = info.tags.map(t => tagsCache.get(t));
+  tagSqlList = "(" + tagSqlList.join(", ") + ")";
+  let query = async (db) => {
+    await db.executeCached(
+      `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
+              b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
+              b.id AS _id, b.parent AS _parentId,
+              (SELECT count(*) FROM moz_bookmarks WHERE parent = b.id) AS _childCount,
+               p.parent AS _grandParentId, b.syncStatus AS _syncStatus
+      FROM moz_bookmarks b
+      LEFT JOIN moz_bookmarks p ON p.id = b.parent
+      LEFT JOIN moz_places h ON h.id = b.fk
+      WHERE (SELECT COUNT(1) FROM moz_tags_relation
+             WHERE place_id = b.fk AND tag_id IN ${ tagSqlList }) = :tagIdSqlListLength
+      AND _grandParentId <> :tagsFolderId
+      ORDER BY b.lastModified DESC`,
+      { tagIdSqlListLength: info.tags.length, tagsFolderId },
+      row => {
+        if (!returnRow) {
+          // Store first row for returning.
+          returnRow = rowToBookmarkItem(row);
+        }
+
+        if (onResult) {
+          try {
+            onResult(rowToBookmarkItem(row));
+          } catch (ex) {
+            Cu.reportError(ex);
+          }
+        } else {
+          // There is no callback, so we need only the first result, so quit early.
+          throw StopIteration;
+        }
+      });
+    return returnRow;
+  };
+  if (concurrent) {
+    let db = await PlacesUtils.promiseDBConnection();
+    return query(db);
+  }
+
+  return PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: fetchBookmarksByTags",
+    query);
+}
+
 function fetchRecentBookmarks(numberOfItems) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchRecentBookmarks",
     async function(db) {
       let tagsFolderId = await promiseTagsFolderId();
       let rows = await db.executeCached(
         `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
                 b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
                 NULL AS _id, NULL AS _parentId, NULL AS _childCount, NULL AS _grandParentId,
@@ -1713,16 +2070,45 @@ function fetchBookmarksByParent(info) {
        WHERE p.guid = :parentGuid
        ORDER BY b.position ASC
       `, { parentGuid: info.parentGuid });
 
     return rowsToItemsArray(rows);
   });
 }
 
+// Fetch tags implementation
+
+async function fetchTags(info, concurrent) {
+  if (info.hasOwnProperty("guid")) {
+    // If we have guid of a bookmark, we get the URL using fetch.
+    // This is since we map tags to places (URLs), and not to bookmarks in the schema.
+    let bookmark = await PlacesUtils.bookmarks.fetch(info.guid);
+    info.url = bookmark.url;
+  }
+
+  const queryTask = async (db) => {
+    let rows = await db.executeCached(
+      `SELECT t.tag FROM moz_tags t
+       JOIN moz_tags_relation r ON t.id = r.tag_id
+       JOIN moz_places h ON r.place_id = h.id
+       WHERE h.url_hash = hash(:url) AND url = :url`,
+      { url: info.url.href }
+    );
+    return rows.map(r => r.getResultByIndex(0));
+  };
+
+  if (concurrent) {
+    let db = await PlacesUtils.promiseDBConnection();
+    return queryTask(db);
+  }
+  return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchTags",
+                                           queryTask);
+}
+
 // Remove implementation.
 
 function removeBookmark(item, options) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: removeBookmark",
     async function(db) {
     let urls;
     let isUntagging = item._grandParentId == PlacesUtils.tagsFolderId;
 
@@ -1974,61 +2360,146 @@ function removeSameValueProperties(dest,
         remove = dest[prop] == src[prop];
     }
     if (remove && prop != "guid")
       delete dest[prop];
   }
 }
 
 /**
+ * Strip tags from `addTags` and `removeTags` properties if they already exist or
+ * do not exist (respectively) on the given bookmark item.
+ *
+ * @param info
+ *        bookmark object.
+ * @return a cleaned up bookmark object.
+ */
+async function stripUnchangeableTags(info) {
+  let currentTags = await PlacesUtils.bookmarks.fetchTags({ guid: info.guid });
+  info.addTags = info.addTags.filter(t => !currentTags.includes(t));
+  info.removeTags = info.removeTags.filter(t => currentTags.includes(t));
+  return info;
+}
+
+/**
+ * Check if multiple bookmarks exist for the given URL.
+ *
+ * @param url
+ *        a URL object
+ * @return a promise which resolves when the check completes.
+ * @resolves true if multiple bookmarks exists, false otherwise.
+ * @rejects on any error while checking.
+ */
+async function checkMultipleBookmarks(url) {
+  let count = 0;
+  await PlacesUtils.bookmarks.fetch({ url }, bmark => { count++; });
+  return count > 1;
+}
+
+/**
+ * Convert a mozIStorageRow object to a bookmark object.
+ *
+ * @param row
+ *        a mozIStorageRow object.
+ * @return a bookmark object.
+ */
+function rowToBookmarkItem(row) {
+  let item = {};
+  for (let prop of ["guid", "index", "type"]) {
+    item[prop] = row.getResultByName(prop);
+  }
+  for (let prop of ["dateAdded", "lastModified"]) {
+    let value = row.getResultByName(prop);
+    if (value)
+      item[prop] = PlacesUtils.toDate(value);
+  }
+  for (let prop of ["title", "parentGuid", "url" ]) {
+    let val = row.getResultByName(prop);
+    if (val)
+      item[prop] = prop === "url" ? new URL(val) : val;
+  }
+  for (let prop of ["_id", "_parentId", "_childCount", "_grandParentId",
+                    "_syncStatus"]) {
+    let val = row.getResultByName(prop);
+    if (val !== null) {
+      // These properties should not be returned to the API consumer, thus
+      // they are non-enumerable and removed through Object.assign just before
+      // the object is returned.
+      // Configurable is set to support mergeIntoNewObject overwrites.
+      Object.defineProperty(item, prop, { value: val, enumerable: false,
+                                          configurable: true });
+    }
+  }
+
+  return item;
+}
+
+/**
  * Convert an array of mozIStorageRow objects to an array of bookmark objects.
  *
  * @param rows
  *        the array of mozIStorageRow objects.
  * @return an array of bookmark objects.
  */
 function rowsToItemsArray(rows) {
-  return rows.map(row => {
-    let item = {};
-    for (let prop of ["guid", "index", "type"]) {
-      item[prop] = row.getResultByName(prop);
-    }
-    for (let prop of ["dateAdded", "lastModified"]) {
-      let value = row.getResultByName(prop);
-      if (value)
-        item[prop] = PlacesUtils.toDate(value);
-    }
-    for (let prop of ["title", "parentGuid", "url" ]) {
-      let val = row.getResultByName(prop);
-      if (val)
-        item[prop] = prop === "url" ? new URL(val) : val;
-    }
-    for (let prop of ["_id", "_parentId", "_childCount", "_grandParentId",
-                      "_syncStatus"]) {
-      let val = row.getResultByName(prop);
-      if (val !== null) {
-        // These properties should not be returned to the API consumer, thus
-        // they are non-enumerable and removed through Object.assign just before
-        // the object is returned.
-        // Configurable is set to support mergeIntoNewObject overwrites.
-        Object.defineProperty(item, prop, { value: val, enumerable: false,
-                                                        configurable: true });
-      }
-    }
-
-    return item;
-  });
+  return rows.map(rowToBookmarkItem);
 }
 
 function validateBookmarkObject(input, behavior) {
   return PlacesUtils.validateItemProperties(
     PlacesUtils.BOOKMARK_VALIDATORS, input, behavior);
 }
 
 /**
+ * Inserts a tag into the database, and returns the tag id.
+ * @param tag
+ *        A string, containing a tag name.
+ * @return {Promise} resolves when insertion is complete.
+ * @resolves to the tag id.
+ * @rejects if any error is encountered during insertion.
+ */
+function maybeInsertTag(tag) {
+  return PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: maybeInsertTag",
+    async (db) => {
+      await db.executeCached(
+        `INSERT OR IGNORE INTO moz_tags (tag) VALUES (:tag)`,
+        { tag }
+      );
+      let rows = await db.executeCached(
+        `SELECT id FROM moz_tags WHERE tag = :tag`,
+        { tag }
+      );
+      return parseInt(rows[0].getResultByIndex(0));
+    }
+  );
+}
+
+/**
+ * Changes the name of a tag in the database.
+ * @param oldTag
+ *        a string containing the old tag.
+ * @param newTag
+ *        a string containing the new tag.
+ * @return {Promise} resolves when updation is complete.
+ */
+function replaceTag(oldTag, newTag) {
+  return PlacesUtils.withConnectionWrapper(
+    "Bookmarks.jsm: replaceTag",
+    async (db) => {
+      return db.executeCached(
+        `UPDATE moz_tags SET tag = :newTag
+         WHERE tag = :oldTag`,
+        { oldTag, newTag }
+      );
+    }
+  );
+}
+
+/**
  * Updates frecency for a list of URLs.
  *
  * @param db
  *        the Sqlite.jsm connection handle.
  * @param urls
  *        the array of URLs to update.
  * @param [optional] collapseNotifications
  *        whether we can send just one onManyFrecenciesChanged
@@ -2185,16 +2656,26 @@ async function(db, folderGuids, options)
          WHERE p.guid = :folderGuid
          UNION ALL
          SELECT id FROM moz_bookmarks
          JOIN descendants ON parent = did
        )
        DELETE FROM moz_bookmarks WHERE id IN descendants`, { folderGuid });
   }
 
+  // Remove any tag/place relations as needed.
+  // Note that the checkMultipleBookmarks is necesary because of the
+  // schema(tags-bookmarks) vs api(tags-bookmark) relation.
+  let urls = itemsRemoved.filter(item => "url" in item).map(item => item.url);
+  for (let url of urls) {
+    if(!(await checkMultipleBookmarks(url))) {
+      await removeTagsForBookmark({ url });
+    }
+  }
+
   // Write tombstones for removed items.
   await insertTombstones(db, itemsRemoved, syncChangeDelta);
 
   // Bump the change counter for all tagged bookmarks when removing tag
   // folders.
   await addSyncChangesForRemovedTagFolders(db, itemsRemoved, syncChangeDelta);
 
   // Cleanup orphans.
@@ -2226,17 +2707,17 @@ async function(db, folderGuids, options)
         notify(observers, "onItemChanged", [ entry._id, "tags", false, "",
                                              PlacesUtils.toPRTime(entry.lastModified),
                                              entry.type, entry._parentId,
                                              entry.guid, entry.parentGuid,
                                              "", source ]);
       }
     }
   }
-  return itemsRemoved.filter(item => "url" in item).map(item => item.url);
+  return urls;
 };
 
 /**
  * Tries to insert a new place if it doesn't exist yet.
  * @param url
  *        A valid URL object.
  * @return {Promise} resolved when the operation is complete.
  */
--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -243,21 +243,23 @@ const BOOKMARK_VALIDATORS = Object.freez
     if (typeof(v) === "string")
       return new URL(v);
     if (v instanceof Ci.nsIURI)
       return new URL(v.spec);
     return v;
   },
   source: simpleValidateFunc(v => Number.isInteger(v) &&
                                   Object.values(PlacesUtils.bookmarks.SOURCES).includes(v)),
+  addTags: simpleValidateFunc(v => Array.isArray(v)),
+  removeTags: simpleValidateFunc(v => Array.isArray(v)),
   annos: simpleValidateFunc(v => Array.isArray(v) && v.length),
   keyword: simpleValidateFunc(v => (typeof(v) == "string") && v.length),
   charset: simpleValidateFunc(v => (typeof(v) == "string") && v.length),
   postData: simpleValidateFunc(v => (typeof(v) == "string") && v.length),
-  tags: simpleValidateFunc(v => Array.isArray(v) && v.length),
+  tags: simpleValidateFunc(v => Array.isArray(v) && v.length)
 });
 
 // Sync bookmark records can contain additional properties.
 const SYNC_BOOKMARK_VALIDATORS = Object.freeze({
   // Sync uses Places GUIDs for all records except roots.
   syncId: simpleValidateFunc(v => typeof v == "string" && (
                                   (PlacesSyncUtils.bookmarks.ROOTS.includes(v) ||
                                    PlacesUtils.isValidGuid(v)))),
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_fetch.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_fetch.js
@@ -60,16 +60,23 @@ add_task(async function invalid_input_th
                 /Invalid value for property 'index'/);
   Assert.throws(() => PlacesUtils.bookmarks.fetch({ parentGuid: "123456789012",
                                                     index: null }),
                 /Invalid value for property 'index'/);
   Assert.throws(() => PlacesUtils.bookmarks.fetch({ parentGuid: "123456789012",
                                                     index: -10 }),
                 /Invalid value for property 'index'/);
 
+  Assert.throws(() => PlacesUtils.bookmarks.fetch({ parentGuid: "123456789012",
+                                                   tags: "not an array" }),
+                /Invalid value for property 'tags'/);
+  Assert.throws(() => PlacesUtils.bookmarks.fetch({ parentGuid: "123456789012",
+                                                   tags: [] }),
+                /Invalid value for property 'tags'/);
+
   Assert.throws(() => PlacesUtils.bookmarks.fetch({ url: "http://te st/" }),
                 /Invalid value for property 'url'/);
   Assert.throws(() => PlacesUtils.bookmarks.fetch({ url: null }),
                 /Invalid value for property 'url'/);
   Assert.throws(() => PlacesUtils.bookmarks.fetch({ url: -10 }),
                 /Invalid value for property 'url'/);
 
   Assert.throws(() => PlacesUtils.bookmarks.fetch("123456789012", "test"),
@@ -302,16 +309,130 @@ add_task(async function fetch_byurl() {
   Assert.equal(gAccumulator.results.length, 2);
   gAccumulator.results.forEach(checkBookmarkObject);
   Assert.deepEqual(gAccumulator.results[0], bm5);
 
   // cleanup
   PlacesUtils.tagging.untagURI(uri(bm1.url.href), ["Test Tag"]);
 });
 
+add_task(async function fetch_by_tag() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.fetch({ tags: ["tag1"] },
+                                              gAccumulator.callback);
+
+  checkBookmarkObject(bm2);
+  Assert.equal(gAccumulator.results.length, 1);
+  Assert.deepEqual(gAccumulator.results[0], bm1);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+});
+
+add_task(async function fetch_by_nonexistent_tag() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.fetch({ tags: ["tag2"] },
+                                              gAccumulator.callback);
+
+  Assert.ok(!bm2);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+});
+
+add_task(async function fetch_single_bookmark_with_multiple_tags() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://2.url.com/",
+                                                 addTags: ["tag3", "tag2"] });
+  checkBookmarkObject(bm2);
+
+  let bm3 = await PlacesUtils.bookmarks.fetch({ tags: ["tag1", "tag2"] },
+                                              gAccumulator.callback);
+  checkBookmarkObject(bm3);
+  Assert.equal(gAccumulator.results.length, 1);
+  Assert.deepEqual(gAccumulator.results[0], bm1);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+  await PlacesUtils.bookmarks.remove(bm2.guid);
+});
+
+add_task(async function fetch_multiple_bookmarks_with_single_tag() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://2.url.com/",
+                                                 addTags: ["tag3", "tag2"] });
+  checkBookmarkObject(bm2);
+
+  let bm3 = await PlacesUtils.bookmarks.fetch({ tags: ["tag2"] },
+                                              gAccumulator.callback);
+  checkBookmarkObject(bm3);
+  Assert.equal(gAccumulator.results.length, 2);
+  Assert.deepEqual(gAccumulator.results[0], bm2);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+  await PlacesUtils.bookmarks.remove(bm2.guid);
+});
+
+add_task(async function fetch_single_bookmark_with_multiple_tags() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://2.url.com/",
+                                                 addTags: ["tag3", "tag2"] });
+  checkBookmarkObject(bm2);
+
+  let bm3 = await PlacesUtils.bookmarks.fetch({ tags: ["tag1", "tag2"] },
+                                              gAccumulator.callback);
+  checkBookmarkObject(bm3);
+  Assert.equal(gAccumulator.results.length, 1);
+  Assert.deepEqual(gAccumulator.results[0], bm1);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+  await PlacesUtils.bookmarks.remove(bm2.guid);
+});
+
+add_task(async function fetch_multiple_bookmarks_with_single_tag() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://1.url.com/",
+                                                 addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm1);
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 url: "http://2.url.com/",
+                                                 addTags: ["tag3", "tag2"] });
+  checkBookmarkObject(bm2);
+
+  let bm3 = await PlacesUtils.bookmarks.fetch({ tags: ["tag2"] },
+                                              gAccumulator.callback);
+  checkBookmarkObject(bm3);
+  Assert.equal(gAccumulator.results.length, 2);
+  Assert.deepEqual(gAccumulator.results[0], bm2);
+
+  // cleanup
+  await PlacesUtils.bookmarks.remove(bm1.guid);
+  await PlacesUtils.bookmarks.remove(bm2.guid);
+});
+
 add_task(async function fetch_concurrent() {
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                  url: "http://concurrent.url.com/" });
   checkBookmarkObject(bm1);
 
   let bm2 = await PlacesUtils.bookmarks.fetch({ url: bm1.url },
                                               gAccumulator.callback,
                                               { concurrent: true });
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_fetchTags.js
@@ -0,0 +1,88 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function fetch_url_without_tags() {
+  let bookmark = await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                                      parentGuid: PlacesUtils.bookmarks.unfiledGuid });
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bookmark.url });
+  Assert.equal(tagsArray.length, 0);
+});
+add_task(async function fetch_by_url() {
+  let bookmark = await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                                      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                      addTags: [ "tag1", "tag2" ] });
+
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bookmark.url });
+  checkTagsArray(tagsArray, ["tag1", "tag2"]);
+});
+
+add_task(async function fetch_by_guid() {
+  let bookmark = await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                                      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                      addTags: [ "tag1", "tag2" ] });
+
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ guid: bookmark.guid });
+  checkTagsArray(tagsArray, ["tag1", "tag2"]);
+});
+
+add_task(async function fetch_all() {
+  await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                       parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                       addTags: [ "tag1", "tag2" ] });
+  await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                       parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                       addTags: [ "tag1", "tag3" ] });
+  await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                       parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                       addTags: [ "tag2", "tag4" ] });
+
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags();
+  checkTagsArray(tagsArray, ["tag1", "tag2", "tag3", "tag4"]);
+});
+
+add_task(async function fetch_fails_on_non_bookmark() {
+  const uri = new URL(`http://example.com/${ Math.random() }`);
+  await PlacesTestUtils.addVisits({ uri });
+  let fetchPromise = PlacesUtils.bookmarks.fetchTags({ url: uri });
+  Assert.rejects(fetchPromise, /The URL\/GUID should point to a pre-existing bookmark/);
+});
+
+add_task(async function fetch_fails_on_folder() {
+  let folder = await PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+                                                    parentGuid: PlacesUtils.bookmarks.unfiledGuid });
+  let fetchPromise = PlacesUtils.bookmarks.fetchTags({ guid: folder.guid });
+  Assert.rejects(fetchPromise, /The URL\/GUID should point to a pre-existing bookmark/);
+});
+
+add_task(async function fetch_concurrent_url() {
+  let bookmark = await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                                      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                      addTags: [ "tag1", "tag2" ] });
+
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bookmark.url },
+                                                        null,
+                                                        { concurrent: true });
+  checkTagsArray(tagsArray, ["tag1", "tag2"]);
+});
+
+add_task(async function fetch_concurrent_guid() {
+  let bookmark = await PlacesUtils.bookmarks.insert({ url: `http://example.com/${ Math.random() }`,
+                                                      parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                      addTags: [ "tag1", "tag2" ] });
+
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ guid: bookmark.guid },
+                                                        null,
+                                                        { concurrent: true });
+  checkTagsArray(tagsArray, ["tag1", "tag2"]);
+});
+
+add_task(async function invalid_input_throws() {
+  Assert.throws(() => PlacesUtils.bookmarks.fetchTags(null, "string"),
+                /onResult callback must be a valid function/);
+  Assert.throws(() => PlacesUtils.bookmarks.fetchTags(true),
+                /Input should be a valid object if not null/);
+  Assert.throws(() => PlacesUtils.bookmarks.fetchTags({}),
+                /Unexpected number of conditions provided: 0/);
+  Assert.throws(() => PlacesUtils.bookmarks.fetchTags({url: "url", guid: "guid"}),
+                /Unexpected number of conditions provided: 2/);
+});
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_insert.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_insert.js
@@ -72,16 +72,24 @@ add_task(async function invalid_input_th
                                                      url: longurl }),
                 /Invalid value for property 'url'/);
   Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
                                                      url: NetUtil.newURI(longurl) }),
                 /Invalid value for property 'url'/);
   Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
                                                      url: "te st" }),
                 /Invalid value for property 'url'/);
+  Assert.throws(() => PlacesUtils.bookmarks.insert({ addTags: "tag1" }),
+                /Invalid value for property 'addTags'/);
+  Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+                                                    addTags: [ "tag1" ] }),
+                /Invalid value for property 'addTags'/);
+  Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+                                                    addTags: [ "tag1" ] }),
+                /Invalid value for property 'addTags'/);
 });
 
 add_task(async function invalid_properties_for_bookmark_type() {
   Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      url: "http://www.moz.com/" }),
                 /Invalid value for property 'url'/);
   Assert.throws(() => PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
                                                      url: "http://www.moz.com/" }),
@@ -250,8 +258,60 @@ add_task(async function create_bookmark_
                                                 url: "http://example.com/",
                                                 title: "a bookmark" });
   checkBookmarkObject(bm);
   Assert.equal(bm.parentGuid, PlacesUtils.bookmarks.unfiledGuid);
   Assert.equal(bm.type, PlacesUtils.bookmarks.TYPE_BOOKMARK);
   Assert.equal(bm.url.href, "http://example.com/");
   Assert.equal(bm.title, "a bookmark");
 });
+
+add_task(async function create_bookmark_with_new_tags() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                url: `http://1.example.com/${ Math.random() }`,
+                                                title: "a bookmark",
+                                                addTags: [ "tag1", "tag2" ]});
+  checkBookmarkObject(bm1);
+
+  // At this point, getting all the tags should get tag1 and tag2
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags();
+  checkTagsArray(tagsArray, ["tag1", "tag2"]);
+
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 url: `http://2.example.com/${ Math.random() }`,
+                                            title: "a bookmark",
+                                            addTags: [ "tag1" ]});
+
+  checkBookmarkObject(bm2);
+
+  // Fetching by guid or URL should give the same result.
+  tagsArray = await PlacesUtils.bookmarks.fetchTags({ guid: bm2.guid });
+  checkTagsArray(tagsArray, ["tag1"]);
+
+  tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bm2.url });
+  checkTagsArray(tagsArray, ["tag1"]);
+});
+
+add_task(async function create_bookmark_with_different_case_tag() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                url: `http://1.example.com/${ Math.random() }`,
+                                                title: "a bookmark",
+                                                addTags: [ "tag1" ]});
+  checkBookmarkObject(bm1);
+  let tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bm1.url });
+  checkTagsArray(tagsArray, ["tag1"]);
+
+  let bm2 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 url: `http://2.example.com/${ Math.random() }`,
+                                                 title: "a bookmark",
+                                                 addTags: [ "tAg1" ]});
+  checkBookmarkObject(bm2);
+  // At this point, the tag should be associated with both the bookmarks,
+  // and use the casing of the later addition.
+  tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bm1.url });
+  checkTagsArray(tagsArray, ["tAg1"]);
+  tagsArray = await PlacesUtils.bookmarks.fetchTags({ url: bm2.url });
+  checkTagsArray(tagsArray, ["tAg1"]);
+});
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_insertTree.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_insertTree.js
@@ -322,8 +322,35 @@ add_task(async function insert_many_non_
     if (bm.type == PlacesUtils.bookmarks.TYPE_BOOKMARK) {
       Assert.greater(frecencyForUrl(bm.url), 0, "Check frecency has been updated for bookmark " + bm.url);
     }
     Assert.equal(bm.parentGuid, PlacesUtils.bookmarks.unfiledGuid);
   }
   Assert.equal(obsInvoked, bms.length);
   Assert.equal(obsInvoked, 6);
 });
+
+add_task(async function create_bookmarks_with_tags() {
+  let bmArray = await PlacesUtils.bookmarks.insertTree({children: [{
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    title: "Test",
+    children: [
+      {
+        url: "http://1.example.com",
+        title: "Bookmark1",
+        tags: ["tag1", "tag2"]
+      },
+      {
+        url: "http://2.example.com",
+        title: "Bookmark 2",
+        tags: ["tag1"]
+      }
+    ]
+  }], guid: PlacesUtils.bookmarks.unfiledGuid});
+
+  for (let bm of bmArray) {
+    checkBookmarkObject(bm);
+  }
+  let tags = await PlacesUtils.bookmarks.fetchTags({ url: bmArray[1].url });
+  checkTagsArray(tags, ["tag1", "tag2"]);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bmArray[2].url });
+  checkTagsArray(tags, ["tag1"]);
+});
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
@@ -191,47 +191,51 @@ add_task(async function remove_folder() 
 
 add_task(async function test_contents_removed() {
   let folder1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                                  type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
                                                  url: "http://example.com/",
-                                                 title: "" });
+                                                 title: "",
+                                                 addTags: ["tag1"] });
 
   let manyFrencenciesPromise = promiseManyFrecenciesChanged();
   await PlacesUtils.bookmarks.remove(folder1);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder1.guid)), null);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(bm1.guid)), null);
 
+  Assert.ok(!(await checkPlaceTagRelation(bm1.url)));
   // We should get an onManyFrecenciesChanged notification with the removal of
   // a folder with children.
   await manyFrencenciesPromise;
 });
 
 
 add_task(async function test_nested_contents_removed() {
   let folder1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   let folder2 = await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: folder2.guid,
                                                  type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
                                                  url: "http://example.com/",
-                                                 title: "" });
+                                                 title: "",
+                                                 addTags: ["tag1"] });
 
   let manyFrencenciesPromise = promiseManyFrecenciesChanged();
   await PlacesUtils.bookmarks.remove(folder1);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder1.guid)), null);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(folder2.guid)), null);
   Assert.strictEqual((await PlacesUtils.bookmarks.fetch(bm1.guid)), null);
 
+  Assert.ok(!(await checkPlaceTagRelation(bm1.url)));
   // We should get an onManyFrecenciesChanged notification with the removal of
   // a folder with children.
   await manyFrencenciesPromise;
 });
 
 add_task(async function remove_folder_empty_title() {
   let bm1 = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                  type: PlacesUtils.bookmarks.TYPE_FOLDER,
@@ -268,8 +272,46 @@ add_task(async function test_nested_cont
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   await PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                        type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                        title: "a folder" });
   await Assert.rejects(PlacesUtils.bookmarks.remove(folder1, {preventRemovalOfNonEmptyFolders: true}),
                        /Cannot remove a non-empty folder./);
 });
+
+add_task(async function test_tag_relation_removed_on_bookmark_remove() {
+  let bm = await PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                url: "http://1.example.com",
+                                                addTags: ["tag1"] });
+  checkBookmarkObject(bm);
+
+  let relation = await checkPlaceTagRelation(bm.url, "tag1");
+  Assert.ok(relation);
+
+  await PlacesUtils.bookmarks.remove({ guid: bm.guid });
+  relation = await checkPlaceTagRelation(bm.url, "tag1");
+  Assert.ok(!relation);
+});
+
+add_task(async function test_tag_relation_not_removed_on_bookmark_remove() {
+  let bm = await PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                url: "http://1.example.com",
+                                                title: "bookmark1",
+                                                addTags: ["tag1"] });
+  checkBookmarkObject(bm);
+  bm = await PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                            parentGuid: PlacesUtils.bookmarks.mobileGuid,
+                                            url: "http://1.example.com",
+                                            title: "bookmark2",
+                                            addTags: ["tag1"] });
+  checkBookmarkObject(bm);
+
+  let relation = await checkPlaceTagRelation(bm.url, "tag1");
+  Assert.ok(relation);
+
+  await PlacesUtils.bookmarks.remove({ guid: bm.guid });
+
+  relation = await checkPlaceTagRelation(bm.url, "tag1");
+  Assert.ok(relation);
+});
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_removeTagsIfEmpty.js
@@ -0,0 +1,80 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+async function isTagInDatabase(tag) {
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.executeCached(
+    `SELECT 1 FROM moz_tags WHERE tag = :tag`,
+    { tag }
+  );
+  return rows.length ? true : false;
+}
+
+/**
+ * This test makes sure that when we remove a tag from a bookmark, that
+ * tag is removed from moz_tags if and only if no other bookmark is linked to that tag.
+ * Conversely, it also determines that the tags are not removed needlessly.
+ */
+
+add_task(async function test_removeTagsIfEmpty_on_remove_item() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ url: "http://1.example.com/",
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 addTags: ["tag1", "tag2"] });
+  let bm2 = await PlacesUtils.bookmarks.insert({ url: "http://2.example.com/",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag2"] });
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+  await PlacesUtils.bookmarks.remove({ guid: bm1.guid });
+
+  let tags = await PlacesUtils.bookmarks.fetchTags();
+  checkTagsArray(tags, ["tag2"]);
+  Assert.ok(!(await isTagInDatabase("tag1")));
+  Assert.ok((await isTagInDatabase("tag2")));
+});
+
+add_task(async function test_removeTagsIfEmpty_on_update() {
+  let bm1 = await PlacesUtils.bookmarks.insert({ url: "http://1.example.com/",
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 addTags: ["tag1", "tag2"] });
+  let bm2 = await PlacesUtils.bookmarks.insert({ url: "http://2.example.com/",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag2"] });
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+  await PlacesUtils.bookmarks.update({ guid: bm1.guid,
+                                       addTags: ["tag3"],
+                                       removeTags: ["tag1", "tag2"] });
+  let tags = await PlacesUtils.bookmarks.fetchTags();
+  checkTagsArray(tags, ["tag2", "tag3"]);
+  Assert.ok((await isTagInDatabase("tag2")));
+  Assert.ok((await isTagInDatabase("tag3")));
+  Assert.ok(!(await isTagInDatabase("tag1")));
+});
+
+add_task(async function test_removeTagsIfEmpty_on_remove_folder() {
+  let unfiledFolder = await PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                           type: PlacesUtils.bookmarks.TYPE_FOLDER });
+  let bm1 = await PlacesUtils.bookmarks.insert({ url: "http://1.example.com/",
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 parentGuid: unfiledFolder.guid,
+                                                 addTags: ["tag1", "tag2"] });
+  let bm2 = await PlacesUtils.bookmarks.insert({ url: "http://2.example.com/",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag2"] });
+  checkBookmarkObject(unfiledFolder);
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+
+  await PlacesUtils.bookmarks.remove({ guid: unfiledFolder.guid });
+
+  let tags = await PlacesUtils.bookmarks.fetchTags();
+  checkTagsArray(tags, ["tag2"]);
+  Assert.ok(!(await isTagInDatabase("tag1")));
+  Assert.ok((await isTagInDatabase("tag2")));
+});
--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_update.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_update.js
@@ -387,8 +387,143 @@ add_task(async function update_move_appe
   ensurePosition(sep_2, folder_b.guid, 1);
   sep_1 = await PlacesUtils.bookmarks.fetch(sep_1.guid);
   ensurePosition(sep_1, folder_a.guid, 0);
   sep_3 = await PlacesUtils.bookmarks.fetch(sep_3.guid);
   ensurePosition(sep_3, folder_b.guid, 0);
   sep_2 = await PlacesUtils.bookmarks.fetch(sep_2.guid);
   ensurePosition(sep_2, folder_b.guid, 1);
 });
+
+add_task(async function update_tags_add() {
+  let bm = await PlacesUtils.bookmarks.insert({ url: "http://1.example.com/",
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm);
+  let tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag1", "tag2"]);
+
+  bm = await PlacesUtils.bookmarks.update({ guid: bm.guid,
+                                            addTags: ["tag1", "tag3"] });
+  checkBookmarkObject(bm);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag1", "tag2", "tag3"]);
+});
+
+add_task(async function update_tags_remove() {
+  let bm = await PlacesUtils.bookmarks.insert({ url: "http://2.example.com/",
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm);
+  let tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag1", "tag2"]);
+
+  bm = await PlacesUtils.bookmarks.update({ guid: bm.guid,
+                                            removeTags: ["tag1", "tag3"] });
+  checkBookmarkObject(bm);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag2"]);
+});
+
+add_task(async function update_tags_add_remove() {
+  let bm = await PlacesUtils.bookmarks.insert({ url: "http://2.example.com/",
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                addTags: ["tag2"] });
+  checkBookmarkObject(bm);
+  let tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag2"]);
+
+  bm = await PlacesUtils.bookmarks.update({ guid: bm.guid,
+                                            addTags: ["tag1"],
+                                            removeTags: ["tag2"] });
+  checkBookmarkObject(bm);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm.url });
+  checkTagsArray(tags, ["tag1"]);
+});
+
+add_task(async function update_url_with_tags() {
+  // There are four cases to check here, as explained in the code.
+  // Case1: There is only one bookmark with the URL1, and none with URL2.
+  let bm = await PlacesUtils.bookmarks.insert({ url: "http://11.example.com/",
+                                                parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                addTags: ["tag1", "tag2"] });
+  checkBookmarkObject(bm);
+
+  let bmUpdated = await PlacesUtils.bookmarks.update({ guid: bm.guid,
+                                            url: "http://11.example.com/u",
+                                            addTags: ["tag3"],
+                                            removeTags: ["tag2"] });
+  checkBookmarkObject(bmUpdated);
+  Assert.ok(!(await checkPlaceTagRelation(bm.url)),
+            "URL/Tag relation should not exist in moz_tags_relation if bookmark doesn't exist.");
+  let tags = await PlacesUtils.bookmarks.fetchTags({ url: bmUpdated.url });
+  checkTagsArray(tags, ["tag1", "tag3"]);
+
+  // Case 2: There are 2 bookmarks with the same URL1, and none with URL2.
+  let bm1 = await PlacesUtils.bookmarks.insert({ url: "http://21.example.com/",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag1", "tag2"] });
+  let bm2 = await PlacesUtils.bookmarks.insert({ url: "http://21.example.com/",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag3", "tag4"] });
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+  bm1 = await PlacesUtils.bookmarks.update({ guid: bm1.guid,
+                                             url: "http://21.example.com/u",
+                                             addTags: ["tag3"],
+                                             removeTags: ["tag2"] });
+  checkBookmarkObject(bm1);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm1.url });
+  checkTagsArray(tags, ["tag1", "tag3", "tag4"]);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm2.url });
+  checkTagsArray(tags, ["tag1", "tag2", "tag3", "tag4"]);
+
+  // Case 3: There is only 1 bookmark with URL1, and a pre-existing bookmark with URL2.
+  bm1 = await PlacesUtils.bookmarks.insert({ url: "http://31.example.com/",
+                                             parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                             type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                             addTags: ["tag1", "tag2"] });
+  bm2 = await PlacesUtils.bookmarks.insert({ url: "http://31.example.com/u",
+                                             parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                             type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                             addTags: ["tag3", "tag4"] });
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+  bm1 = await PlacesUtils.bookmarks.update({ guid: bm1.guid,
+                                             url: "http://31.example.com/u",
+                                             addTags: ["tag5"],
+                                             removeTags: ["tag2"] });
+  checkBookmarkObject(bm1);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm1.url });
+  checkTagsArray(tags, ["tag1", "tag3", "tag4", "tag5"]);
+
+  // Case 4: There are 2 bookmarks with the same URL1, and a pre-existing bookmark with URL2.
+  bm1 = await PlacesUtils.bookmarks.insert({ url: "http://41.example.com/",
+                                             parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                             type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                             addTags: ["tag1", "tag2"] });
+  bm2 = await PlacesUtils.bookmarks.insert({ url: "http://41.example.com/",
+                                             parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                             type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                             addTags: ["tag3", "tag4"] });
+  let bm3 = await PlacesUtils.bookmarks.insert({ url: "http://41.example.com/u",
+                                                 parentGuid: PlacesUtils.bookmarks.unfiledGuid,
+                                                 type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                 addTags: ["tag5", "tag6"] });
+  checkBookmarkObject(bm1);
+  checkBookmarkObject(bm2);
+  checkBookmarkObject(bm3);
+  bm1 = await PlacesUtils.bookmarks.update({ guid: bm1.guid,
+                                             url: "http://41.example.com/u",
+                                             addTags: ["tag7"],
+                                             removeTags: ["tag2"] });
+  checkBookmarkObject(bm1);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm1.url });
+  checkTagsArray(tags, ["tag1", "tag3", "tag4", "tag5", "tag6", "tag7"]);
+  tags = await PlacesUtils.bookmarks.fetchTags({ url: bm2.url });
+  checkTagsArray(tags, ["tag1", "tag2", "tag3", "tag4"]);
+});
--- a/toolkit/components/places/tests/bookmarks/xpcshell.ini
+++ b/toolkit/components/places/tests/bookmarks/xpcshell.ini
@@ -24,21 +24,23 @@ skip-if = toolkit == 'android'
 [test_997030-bookmarks-html-encode.js]
 [test_1129529.js]
 [test_async_observers.js]
 [test_bmindex.js]
 [test_bookmarkstree_cache.js]
 [test_bookmarks.js]
 [test_bookmarks_eraseEverything.js]
 [test_bookmarks_fetch.js]
+[test_bookmarks_fetchTags.js]
 [test_bookmarks_getRecent.js]
 [test_bookmarks_insert.js]
 [test_bookmarks_insertTree.js]
 [test_bookmarks_notifications.js]
 [test_bookmarks_remove.js]
+[test_bookmarks_removeTagsIfEmpty.js]
 [test_bookmarks_reorder.js]
 [test_bookmarks_search.js]
 [test_bookmarks_update.js]
 [test_changeBookmarkURI.js]
 [test_getBookmarkedURIFor.js]
 [test_keywords.js]
 [test_nsINavBookmarkObserver.js]
 [test_protectRoots.js]
--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -825,16 +825,59 @@ function checkBookmarkObject(info) {
   Assert.ok(typeof info.index == "number", "index should be a number");
   Assert.ok(info.dateAdded.constructor.name == "Date", "dateAdded should be a Date");
   Assert.ok(info.lastModified.constructor.name == "Date", "lastModified should be a Date");
   Assert.ok(info.lastModified >= info.dateAdded, "lastModified should never be smaller than dateAdded");
   Assert.ok(typeof info.type == "number", "type should be a number");
 }
 
 /**
+ * Ensures presence of exactly expectedTags in actualTags.
+ */
+function checkTagsArray(actualTags, expectedTags) {
+  // Null/undefined should not be passed here.
+  Assert.ok(actualTags);
+  for (let tag of actualTags) {
+    Assert.ok(expectedTags.includes(tag));
+  }
+  Assert.equal(actualTags.length, expectedTags.length);
+}
+
+/**
+ * Check if a relation exists in the moz_tags_relation table.
+ * `fetchTags` is insufficient because it only checks bookmark/tag relations,
+ * not url/tags relations (and throws if that URL isn't bookmarked).
+ *
+ * @param url URL of the entry in moz_places.
+ * @param tag [optional] name of the tag in moz_tags.
+              if null or not given, will check for presence of any tag for URL.
+ * @return {Promise}
+ * @resolves true if a relation exists, else false.
+ * @rejects if any error is encountered while checking.
+ */
+async function checkPlaceTagRelation(url, tag = null) {
+  let params = { url: url.href };
+  let tagQueryFragment = "";
+  if (tag) {
+    tagQueryFragment = `AND tag_id = (SELECT id FROM moz_tags
+                                      WHERE tag = :tag)`;
+    params.tag = tag;
+  }
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.executeCached(
+     `SELECT 1 FROM moz_tags_relation
+      WHERE place_id = (SELECT id FROM moz_places WHERE url_hash = hash(:url)
+                        AND url = :url)
+      ${ tagQueryFragment }
+      LIMIT 1`,
+    params);
+  return rows.length ? true : false;
+}
+
+/**
  * Reads foreign_count value for a given url.
  */
 async function foreign_count(url) {
   if (url instanceof Ci.nsIURI)
     url = url.spec;
   let db = await PlacesUtils.promiseDBConnection();
   let rows = await db.executeCached(
     `SELECT foreign_count FROM moz_places