Bug 1322235: Part 1 - Add native MatchPattern and MatchGlob bindings. r=billm,aswan
authorKris Maglione <maglione.k@gmail.com>
Wed, 24 May 2017 14:57:29 -0700
changeset 362249 94a3fb9eb7e4c933ae318ff9b0a5bc9a3ac28e75
parent 362248 8726e36dafe1c875d86b33b5885f6b9e6d1a5a12
child 362250 50e2a20caa7a189c0ed5a8679f483a5b10100aaf
push id31966
push userarchaeopteryx@coole-files.de
push dateMon, 05 Jun 2017 09:06:08 +0000
treeherdermozilla-central@275588f4d852 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbillm, aswan
bugs1322235
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1322235: Part 1 - Add native MatchPattern and MatchGlob bindings. r=billm,aswan Bill, can you please review the binding code, and the general sanity of the platform code. Andrew and zombie, can you please matching algorithms and tests. Change summary: The existing JavaScript matching code works well overall, but it needs to be called a lot, particularly from hot code paths. In most cases, the overhead of the matching code on its own adds up enough to cause a problem. When we have to call out to JavaScript via XPConnect to make a policy decision, it adds up even more. These classes solve both of these problems by a) being very fast, and b) being accessible directly from C++. They are particularly optimized for the common cases where only literal or prefix matches are required, and they take special steps to avoid virtual calls wherever possible, and caching computed URL values so that they can be reused across many match operations without additional overhead. MozReview-Commit-ID: BZzPZDQRnl
dom/base/nsGkAtomList.h
dom/bindings/Bindings.conf
dom/webidl/MatchGlob.webidl
dom/webidl/MatchPattern.webidl
dom/webidl/moz.build
toolkit/components/extensions/MatchGlob.h
toolkit/components/extensions/MatchPattern.cpp
toolkit/components/extensions/MatchPattern.h
toolkit/components/extensions/moz.build
toolkit/components/extensions/test/xpcshell/test_MatchPattern.js
toolkit/components/extensions/test/xpcshell/xpcshell.ini
--- a/dom/base/nsGkAtomList.h
+++ b/dom/base/nsGkAtomList.h
@@ -409,16 +409,17 @@ GK_ATOM(expr, "expr")
 GK_ATOM(extends, "extends")
 GK_ATOM(extensionElementPrefixes, "extension-element-prefixes")
 GK_ATOM(face, "face")
 GK_ATOM(fallback, "fallback")
 GK_ATOM(_false, "false")
 GK_ATOM(farthest, "farthest")
 GK_ATOM(field, "field")
 GK_ATOM(fieldset, "fieldset")
+GK_ATOM(file, "file")
 GK_ATOM(figcaption, "figcaption")
 GK_ATOM(figure, "figure")
 GK_ATOM(fixed, "fixed")
 GK_ATOM(flags, "flags")
 GK_ATOM(flex, "flex")
 GK_ATOM(flexgroup, "flexgroup")
 GK_ATOM(flip, "flip")
 GK_ATOM(floating, "floating")
@@ -2003,16 +2004,20 @@ GK_ATOM(onuserproximity, "onuserproximit
 GK_ATOM(ondevicelight, "ondevicelight")
 
 // MediaDevices device change event
 GK_ATOM(ondevicechange, "ondevicechange")
 
 // HTML element attributes that only exposed to XBL and chrome content
 GK_ATOM(mozinputrangeignorepreventdefault, "mozinputrangeignorepreventdefault")
 
+// WebExtensions
+GK_ATOM(http, "http")
+GK_ATOM(https, "https")
+
 //---------------------------------------------------------------------------
 // Special atoms
 //---------------------------------------------------------------------------
 
 // Node types
 GK_ATOM(cdataTagName, "#cdata-section")
 GK_ATOM(commentTagName, "#comment")
 GK_ATOM(documentNodeName, "#document")
--- a/dom/bindings/Bindings.conf
+++ b/dom/bindings/Bindings.conf
@@ -567,16 +567,29 @@ DOMInterfaces = {
     'wrapperCache': False,
 },
 
 'LocalMediaStream': {
     'headerFile': 'DOMMediaStream.h',
     'nativeType': 'mozilla::DOMLocalMediaStream'
 },
 
+'MatchGlob': {
+    'nativeType': 'mozilla::extensions::MatchGlob',
+},
+
+'MatchPattern': {
+    'nativeType': 'mozilla::extensions::MatchPattern',
+},
+
+'MatchPatternSet': {
+    'headerFile': 'mozilla/extensions/MatchPattern.h',
+    'nativeType': 'mozilla::extensions::MatchPatternSet',
+},
+
 'MediaKeys' : {
     'implicitJSContext': [ 'createSession']
 },
 
 'MediaStream': {
     'headerFile': 'DOMMediaStream.h',
     'nativeType': 'mozilla::DOMMediaStream'
 },
@@ -1684,16 +1697,18 @@ def addExternalIface(iface, nativeType=N
     if not nativeType is None:
         domInterface['nativeType'] = nativeType
     if not headerFile is None:
         domInterface['headerFile'] = headerFile
     domInterface['notflattened'] = notflattened
     DOMInterfaces[iface] = domInterface
 
 addExternalIface('ApplicationCache', nativeType='nsIDOMOfflineResourceList')
+addExternalIface('Cookie', nativeType='nsICookie2',
+                 headerFile='nsICookie2.h', notflattened=True)
 addExternalIface('Counter')
 addExternalIface('RTCDataChannel', nativeType='nsIDOMDataChannel')
 addExternalIface('HitRegionOptions', nativeType='nsISupports')
 addExternalIface('imgINotificationObserver', nativeType='imgINotificationObserver')
 addExternalIface('imgIRequest', nativeType='imgIRequest', notflattened=True)
 addExternalIface('MenuBuilder', nativeType='nsIMenuBuilder', notflattened=True)
 addExternalIface('MozControllers', nativeType='nsIControllers')
 addExternalIface('MozFrameLoader', nativeType='nsIFrameLoader', notflattened=True)
new file mode 100644
--- /dev/null
+++ b/dom/webidl/MatchGlob.webidl
@@ -0,0 +1,24 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/**
+ * Represents a simple glob pattern matcher. Any occurrence of "*" in the glob
+ * pattern matches any literal string of characters in the string being
+ * compared. Additionally, if created with `allowQuestion = true`, any
+ * occurrence of "?" in the glob matches any single literal character.
+ */
+[Constructor(DOMString glob, optional boolean allowQuestion = true),
+ ChromeOnly, Exposed=(Window,System)]
+interface MatchGlob {
+  /**
+   * Returns true if the string matches the glob.
+   */
+  boolean matches(DOMString string);
+
+  /**
+   * The glob string this MatchGlob represents.
+   */
+  [Constant]
+  readonly attribute DOMString glob;
+};
new file mode 100644
--- /dev/null
+++ b/dom/webidl/MatchPattern.webidl
@@ -0,0 +1,120 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+interface Cookie;
+interface URI;
+
+/**
+ * A URL match pattern as used by the WebExtension and Chrome extension APIs.
+ *
+ * A match pattern is a string with one of the following formats:
+ *
+ *  - "<all_urls>"
+ *    The literal string "<all_urls>" matches any URL with a supported
+ *    protocol.
+ *
+ *  - <proto>://<host>/<path>
+ *    A URL pattern with the following placeholders:
+ *
+ *    - <proto>
+ *      The protocol to match, or "*" to match either "http" or "https".
+ *    - <host>
+ *      The hostname to match. May be either a complete, literal hostname to
+ *      match a specific host, the wildcard character "*", to match any host,
+ *      or a subdomain pattern, with "*." followed by a domain name, to match
+ *      that domain name or any subdomain thereof.
+ *    - <path>
+ *      A glob pattern for paths to match. A "*" may appear anywhere within
+ *      the path, and will match any string of characters. If no "*" appears,
+ *      the URL path must exactly match the pattern path.
+ */
+[Constructor(DOMString pattern, optional MatchPatternOptions options),
+ ChromeOnly, Exposed=(Window,System)]
+interface MatchPattern {
+  /**
+   * Returns true if the given URI matches the pattern.
+   *
+   * If explicit is true, only explicit domain matches, without wildcards, are
+   * considered.
+   */
+  boolean matches(URI uri, optional boolean explicit = false);
+
+  /**
+   * Returns true if a URL exists which a) would be able to access the given
+   * cookie, and b) would be matched by this match pattern.
+   */
+  boolean matchesCookie(Cookie cookie);
+
+  /**
+   * Returns true if this pattern will match any host which would be matched
+   * by the given pattern.
+   */
+  boolean subsumes(MatchPattern pattern);
+
+  /**
+   * Returns true if there is any host which would be matched by both this
+   * pattern and the given pattern.
+   */
+  boolean overlaps(MatchPattern pattern);
+
+  /**
+   * The match pattern string represented by this pattern.
+   */
+  [Constant]
+  readonly attribute DOMString pattern;
+};
+
+/**
+ * A set of MatchPattern objects, which implements the MatchPattern API and
+ * matches when any of its sub-patterns matches.
+ */
+[Constructor(sequence<(DOMString or MatchPattern)> patterns, optional MatchPatternOptions options),
+ ChromeOnly, Exposed=(Window,System)]
+interface MatchPatternSet {
+  /**
+   * Returns true if the given URI matches any sub-pattern.
+   *
+   * If explicit is true, only explicit domain matches, without wildcards, are
+   * considered.
+   */
+  boolean matches(URI uri, optional boolean explicit = false);
+
+  /**
+   * Returns true if any sub-pattern matches the given cookie.
+   */
+  boolean matchesCookie(Cookie cookie);
+
+  /**
+   * Returns true if any sub-pattern subsumes the given pattern.
+   */
+  boolean subsumes(MatchPattern pattern);
+
+  /**
+   * Returns true if any sub-pattern overlaps the given pattern.
+   */
+  boolean overlaps(MatchPattern pattern);
+
+  /**
+   * Returns true if any sub-pattern overlaps any sub-pattern the given
+   * pattern set.
+   */
+  boolean overlaps(MatchPatternSet patternSet);
+
+  /**
+   * Returns true if any sub-pattern overlaps *every* sub-pattern in the given
+   * pattern set.
+   */
+  boolean overlapsAll(MatchPatternSet patternSet);
+
+  [Cached, Constant, Frozen]
+  readonly attribute sequence<MatchPattern> patterns;
+};
+
+dictionary MatchPatternOptions {
+  /**
+   * If true, the path portion of the pattern is ignored, and replaced with a
+   * wildcard. The `pattern` property is updated to reflect this.
+   */
+  boolean ignorePath = false;
+};
--- a/dom/webidl/moz.build
+++ b/dom/webidl/moz.build
@@ -658,16 +658,18 @@ WEBIDL_FILES = [
     'KeyframeAnimationOptions.webidl',
     'KeyframeEffect.webidl',
     'KeyIdsInitData.webidl',
     'LegacyQueryInterface.webidl',
     'LinkStyle.webidl',
     'ListBoxObject.webidl',
     'LocalMediaStream.webidl',
     'Location.webidl',
+    'MatchGlob.webidl',
+    'MatchPattern.webidl',
     'MediaDeviceInfo.webidl',
     'MediaDevices.webidl',
     'MediaElementAudioSourceNode.webidl',
     'MediaEncryptedEvent.webidl',
     'MediaError.webidl',
     'MediaKeyError.webidl',
     'MediaKeyMessageEvent.webidl',
     'MediaKeys.webidl',
new file mode 100644
--- /dev/null
+++ b/toolkit/components/extensions/MatchGlob.h
@@ -0,0 +1,98 @@
+/* -*-  Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_extensions_MatchGlob_h
+#define mozilla_extensions_MatchGlob_h
+
+#include "mozilla/dom/BindingDeclarations.h"
+#include "mozilla/dom/MatchGlobBinding.h"
+
+#include "jspubtd.h"
+#include "js/RootingAPI.h"
+
+#include "nsCOMPtr.h"
+#include "nsCycleCollectionParticipant.h"
+#include "nsISupports.h"
+#include "nsWrapperCache.h"
+
+namespace mozilla {
+namespace extensions {
+
+class MatchPattern;
+
+class MatchGlob final : public nsISupports
+                      , public nsWrapperCache
+{
+public:
+  NS_DECL_CYCLE_COLLECTING_ISUPPORTS
+  NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS(MatchGlob)
+
+  static already_AddRefed<MatchGlob>
+  Constructor(dom::GlobalObject& aGlobal, const nsAString& aGlob, bool aAllowQuestion,
+              ErrorResult& aRv);
+
+  bool Matches(const nsAString& aString) const;
+
+  bool IsWildcard() const
+  {
+    return mIsPrefix && mPathLiteral.IsEmpty();
+  }
+
+  void GetGlob(nsAString& aGlob) const
+  {
+    aGlob = mGlob;
+  }
+
+  nsISupports* GetParentObject() const { return mParent; }
+
+  virtual JSObject* WrapObject(JSContext* aCx, JS::HandleObject aGivenProto) override;
+
+protected:
+  virtual ~MatchGlob();
+
+private:
+  friend class MatchPattern;
+
+  explicit MatchGlob(nsISupports* aParent) : mParent(aParent) {}
+
+  void Init(JSContext* aCx, const nsAString& aGlob, bool aAllowQuestion, ErrorResult& aRv);
+
+  nsCOMPtr<nsISupports> mParent;
+
+  // The original glob string that this glob object represents.
+  nsString mGlob;
+
+  // The literal path string to match against. If this contains a non-void
+  // value, the glob matches against this exact literal string, rather than
+  // performng a pattern match. If mIsPrefix is true, the literal must appear
+  // at the start of the matched string. If it is false, the the literal must
+  // be exactly equal to the matched string.
+  nsString mPathLiteral;
+  bool mIsPrefix = false;
+
+  // The regular expression object which is equivalent to this glob pattern.
+  // Used for matching if, and only if, mPathLiteral is non-void.
+  JS::Heap<JSObject*> mRegExp;
+};
+
+class MatchGlobSet final : public nsTArray<RefPtr<MatchGlob>>
+{
+public:
+  // Note: We can't use the nsTArray constructors directly, since the static
+  // analyzer doesn't handle their MOZ_IMPLICIT annotations correctly.
+  MatchGlobSet() {}
+  explicit MatchGlobSet(size_type aCapacity) : nsTArray(aCapacity) {}
+  explicit MatchGlobSet(const nsTArray& aOther) : nsTArray(aOther) {}
+  MOZ_IMPLICIT MatchGlobSet(nsTArray&& aOther) : nsTArray(mozilla::Move(aOther)) {}
+  MOZ_IMPLICIT MatchGlobSet(std::initializer_list<RefPtr<MatchGlob>> aIL) : nsTArray(aIL) {}
+
+  bool Matches(const nsAString& aValue) const;
+};
+
+} // namespace extensions
+} // namespace mozilla
+
+#endif // mozilla_extensions_MatchGlob_h
+
new file mode 100644
--- /dev/null
+++ b/toolkit/components/extensions/MatchPattern.cpp
@@ -0,0 +1,752 @@
+/* -*-  Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/extensions/MatchPattern.h"
+#include "mozilla/extensions/MatchGlob.h"
+
+#include "mozilla/dom/ScriptSettings.h"
+#include "mozilla/HoldDropJSObjects.h"
+#include "mozilla/Unused.h"
+
+#include "nsGkAtoms.h"
+#include "nsIProtocolHandler.h"
+#include "nsIURL.h"
+#include "nsNetUtil.h"
+
+namespace mozilla {
+namespace extensions {
+
+using namespace mozilla::dom;
+
+
+/*****************************************************************************
+ * AtomSet
+ *****************************************************************************/
+
+AtomSet::AtomSet(const nsTArray<nsString>& aElems)
+{
+  mElems.SetCapacity(aElems.Length());
+
+  for (const auto& elem : aElems) {
+    mElems.AppendElement(NS_AtomizeMainThread(elem));
+  }
+
+  SortAndUniquify();
+}
+
+AtomSet::AtomSet(const char** aElems)
+{
+  for (const char** elemp = aElems; *elemp; elemp++) {
+    mElems.AppendElement(NS_Atomize(*elemp));
+  }
+
+  SortAndUniquify();
+}
+
+AtomSet::AtomSet(std::initializer_list<nsIAtom*> aIL)
+{
+  mElems.SetCapacity(aIL.size());
+
+  for (const auto& elem : aIL) {
+    mElems.AppendElement(elem);
+  }
+
+  SortAndUniquify();
+}
+
+void
+AtomSet::SortAndUniquify()
+{
+  mElems.Sort();
+
+  nsIAtom* prev = nullptr;
+  mElems.RemoveElementsBy([&prev] (const RefPtr<nsIAtom>& aAtom) {
+    bool remove = aAtom == prev;
+    prev = aAtom;
+    return remove;
+  });
+
+  mElems.Compact();
+}
+
+bool
+AtomSet::Intersects(const AtomSet& aOther) const
+{
+  for (const auto& atom : *this) {
+    if (aOther.Contains(atom)) {
+      return true;
+    }
+  }
+  for (const auto& atom : aOther) {
+    if (Contains(atom)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+void
+AtomSet::Add(nsIAtom* aAtom)
+{
+  auto index = mElems.IndexOfFirstElementGt(aAtom);
+  if (index == 0 || mElems[index - 1] != aAtom) {
+    mElems.InsertElementAt(index, aAtom);
+  }
+}
+
+void
+AtomSet::Remove(nsIAtom* aAtom)
+{
+  auto index = mElems.BinaryIndexOf(aAtom);
+  if (index != mElems.NoIndex) {
+    mElems.RemoveElementAt(index);
+  }
+}
+
+
+/*****************************************************************************
+ * URLInfo
+ *****************************************************************************/
+
+nsIAtom*
+URLInfo::Scheme() const
+{
+  if (!mScheme) {
+    nsCString scheme;
+    if (NS_SUCCEEDED(mURI->GetScheme(scheme))) {
+      mScheme = NS_AtomizeMainThread(NS_ConvertASCIItoUTF16(scheme));
+    }
+  }
+  return mScheme;
+}
+
+const nsCString&
+URLInfo::Host() const
+{
+  if (mHost.IsVoid()) {
+    Unused << mURI->GetHost(mHost);
+  }
+  return mHost;
+}
+
+const nsString&
+URLInfo::FilePath() const
+{
+  if (mFilePath.IsEmpty()) {
+    nsCString path;
+    nsCOMPtr<nsIURL> url = do_QueryInterface(mURI);
+    if (url && NS_SUCCEEDED(url->GetFilePath(path))) {
+      AppendUTF8toUTF16(path, mFilePath);
+    } else {
+      mFilePath = Path();
+    }
+  }
+  return mFilePath;
+}
+
+const nsString&
+URLInfo::Path() const
+{
+  if (mPath.IsEmpty()) {
+    nsCString path;
+    if (NS_SUCCEEDED(URINoRef()->GetPath(path))) {
+      AppendUTF8toUTF16(path, mPath);
+    }
+  }
+  return mPath;
+}
+
+const nsString&
+URLInfo::Spec() const
+{
+  if (mSpec.IsEmpty()) {
+    nsCString spec;
+    if (NS_SUCCEEDED(URINoRef()->GetSpec(spec))) {
+      AppendUTF8toUTF16(spec, mSpec);
+    }
+  }
+  return mSpec;
+}
+
+nsIURI*
+URLInfo::URINoRef() const
+{
+  if (!mURINoRef) {
+    if (NS_FAILED(mURI->CloneIgnoringRef(getter_AddRefs(mURINoRef)))) {
+      mURINoRef = mURI;
+    }
+  }
+  return mURINoRef;
+}
+
+bool
+URLInfo::InheritsPrincipal() const
+{
+  if (!mInheritsPrincipal.isSome()) {
+    bool inherits = false;
+    nsresult rv = NS_URIChainHasFlags(mURI, nsIProtocolHandler::URI_INHERITS_SECURITY_CONTEXT,
+                                      &inherits);
+    Unused << NS_WARN_IF(NS_FAILED(rv));
+    mInheritsPrincipal.emplace(inherits);
+  }
+  return mInheritsPrincipal.ref();
+}
+
+
+/*****************************************************************************
+ * CookieInfo
+ *****************************************************************************/
+
+bool
+CookieInfo::IsDomain() const
+{
+  if (mIsDomain.isNothing()) {
+    mIsDomain.emplace(false);
+    MOZ_ALWAYS_SUCCEEDS(mCookie->GetIsDomain(mIsDomain.ptr()));
+  }
+  return mIsDomain.ref();
+}
+
+bool
+CookieInfo::IsSecure() const
+{
+  if (mIsSecure.isNothing()) {
+    mIsSecure.emplace(false);
+    MOZ_ALWAYS_SUCCEEDS(mCookie->GetIsSecure(mIsSecure.ptr()));
+  }
+  return mIsSecure.ref();
+}
+
+const nsCString&
+CookieInfo::Host() const
+{
+  if (mHost.IsEmpty()) {
+    MOZ_ALWAYS_SUCCEEDS(mCookie->GetHost(mHost));
+  }
+  return mHost;
+}
+
+const nsCString&
+CookieInfo::RawHost() const
+{
+  if (mRawHost.IsEmpty()) {
+    MOZ_ALWAYS_SUCCEEDS(mCookie->GetRawHost(mRawHost));
+  }
+  return mRawHost;
+}
+
+
+/*****************************************************************************
+ * MatchPattern
+ *****************************************************************************/
+
+const char* PERMITTED_SCHEMES[] = {"http", "https", "file", "ftp", "data", nullptr};
+
+const char* WILDCARD_SCHEMES[] = {"http", "https", nullptr};
+
+/* static */ already_AddRefed<MatchPattern>
+MatchPattern::Constructor(dom::GlobalObject& aGlobal,
+                          const nsAString& aPattern,
+                          const MatchPatternOptions& aOptions,
+                          ErrorResult& aRv)
+{
+  RefPtr<MatchPattern> pattern = new MatchPattern(aGlobal.GetAsSupports());
+  pattern->Init(aGlobal.Context(), aPattern, aOptions.mIgnorePath, aRv);
+  if (aRv.Failed()) {
+    return nullptr;
+  }
+  return pattern.forget();
+}
+
+void
+MatchPattern::Init(JSContext* aCx, const nsAString& aPattern, bool aIgnorePath, ErrorResult& aRv)
+{
+  RefPtr<AtomSet> permittedSchemes = AtomSet::Get<PERMITTED_SCHEMES>();
+
+  mPattern = aPattern;
+
+  if (aPattern.EqualsLiteral("<all_urls>")) {
+    mSchemes = permittedSchemes;
+    mMatchSubdomain = true;
+    return;
+  }
+
+  // The portion of the URL we're currently examining.
+  uint32_t offset = 0;
+  auto tail = Substring(aPattern, offset);
+
+  /***************************************************************************
+   * Scheme
+   ***************************************************************************/
+  int32_t index = aPattern.FindChar(':');
+  if (index <= 0) {
+    aRv.Throw(NS_ERROR_INVALID_ARG);
+    return;
+  }
+
+  nsCOMPtr<nsIAtom> scheme = NS_AtomizeMainThread(StringHead(aPattern, index));
+  if (scheme == nsGkAtoms::_asterisk) {
+    mSchemes = AtomSet::Get<WILDCARD_SCHEMES>();
+  } else if (permittedSchemes->Contains(scheme)) {
+    mSchemes = new AtomSet({scheme});
+  } else {
+    aRv.Throw(NS_ERROR_INVALID_ARG);
+    return;
+  }
+
+  /***************************************************************************
+   * Host
+   ***************************************************************************/
+  offset = index + 1;
+  tail.Rebind(aPattern, offset);
+
+  if (!StringHead(tail, 2).EqualsLiteral("//")) {
+    aRv.Throw(NS_ERROR_INVALID_ARG);
+    return;
+  }
+
+  offset += 2;
+  tail.Rebind(aPattern, offset);
+  index = tail.FindChar('/');
+  if (index < 0) {
+    index = tail.Length();
+  }
+
+  auto host = StringHead(tail, index);
+  if (host.IsEmpty() && scheme != nsGkAtoms::file) {
+    aRv.Throw(NS_ERROR_INVALID_ARG);
+    return;
+  }
+
+  offset += index;
+  tail.Rebind(aPattern, offset);
+
+  if (host.EqualsLiteral("*")) {
+    mMatchSubdomain = true;
+  } else if (StringHead(host, 2).EqualsLiteral("*.")) {
+    mDomain = NS_ConvertUTF16toUTF8(Substring(host, 2));
+    mMatchSubdomain = true;
+  } else {
+    mDomain = NS_ConvertUTF16toUTF8(host);
+  }
+
+  /***************************************************************************
+   * Path
+   ***************************************************************************/
+  if (aIgnorePath) {
+    mPattern.Truncate(offset);
+    mPattern.AppendLiteral("/*");
+    return;
+  }
+
+  auto path = tail;
+  if (path.IsEmpty()) {
+    aRv.Throw(NS_ERROR_INVALID_ARG);
+    return;
+  }
+
+  mPath = new MatchGlob(this);
+  mPath->Init(aCx, path, false, aRv);
+}
+
+
+bool
+MatchPattern::MatchesDomain(const nsACString& aDomain) const
+{
+  if (DomainIsWildcard() || mDomain == aDomain) {
+    return true;
+  }
+
+  if (mMatchSubdomain) {
+    int64_t offset = (int64_t)aDomain.Length() - mDomain.Length();
+    if (offset > 0 && aDomain[offset - 1] == '.' &&
+        Substring(aDomain, offset) == mDomain) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool
+MatchPattern::Matches(const URLInfo& aURL, bool aExplicit) const
+{
+  if (aExplicit && mMatchSubdomain) {
+    return false;
+  }
+
+  if (!mSchemes->Contains(aURL.Scheme())) {
+    return false;
+  }
+
+  if (!DomainIsWildcard() && !MatchesDomain(aURL.Host())) {
+    return false;
+  }
+
+  if (mPath && !mPath->IsWildcard() && !mPath->Matches(aURL.Path())) {
+    return false;
+  }
+
+  return true;
+}
+
+bool
+MatchPattern::MatchesCookie(const CookieInfo& aCookie) const
+{
+  if (!mSchemes->Contains(nsGkAtoms::https) &&
+      (aCookie.IsSecure() || !mSchemes->Contains(nsGkAtoms::http))) {
+    return false;
+  }
+
+  if (MatchesDomain(aCookie.RawHost())) {
+    return true;
+  }
+
+  if (!aCookie.IsDomain()) {
+    return false;
+  }
+
+  // Things get tricker for domain cookies. The extension needs to be able
+  // to read any cookies that could be read by any host it has permissions
+  // for. This means that our normal host matching checks won't work,
+  // since the pattern "*://*.foo.example.com/" doesn't match ".example.com",
+  // but it does match "bar.foo.example.com", which can read cookies
+  // with the domain ".example.com".
+  //
+  // So, instead, we need to manually check our filters, and accept any
+  // with hosts that end with our cookie's host.
+
+  auto& host = aCookie.Host();
+  return StringTail(mDomain, host.Length()) == host;
+}
+
+bool
+MatchPattern::SubsumesDomain(const MatchPattern& aPattern) const
+{
+  if (!mMatchSubdomain && aPattern.mMatchSubdomain && aPattern.mDomain == mDomain) {
+    return false;
+  }
+
+  return MatchesDomain(aPattern.mDomain);
+}
+
+bool
+MatchPattern::Subsumes(const MatchPattern& aPattern) const
+{
+  for (auto& scheme : *aPattern.mSchemes) {
+    if (!mSchemes->Contains(scheme)) {
+      return false;
+    }
+  }
+
+  return SubsumesDomain(aPattern);
+}
+
+bool
+MatchPattern::Overlaps(const MatchPattern& aPattern) const
+{
+  if (!mSchemes->Intersects(*aPattern.mSchemes)) {
+    return false;
+  }
+
+  return SubsumesDomain(aPattern) || aPattern.SubsumesDomain(*this);
+}
+
+
+JSObject*
+MatchPattern::WrapObject(JSContext* aCx, JS::HandleObject aGivenProto)
+{
+  return MatchPatternBinding::Wrap(aCx, this, aGivenProto);
+}
+
+
+NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(MatchPattern, mPath, mParent)
+
+NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(MatchPattern)
+  NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
+  NS_INTERFACE_MAP_ENTRY(nsISupports)
+NS_INTERFACE_MAP_END
+
+NS_IMPL_CYCLE_COLLECTING_ADDREF(MatchPattern)
+NS_IMPL_CYCLE_COLLECTING_RELEASE(MatchPattern)
+
+
+/*****************************************************************************
+ * MatchPatternSet
+ *****************************************************************************/
+
+/* static */ already_AddRefed<MatchPatternSet>
+MatchPatternSet::Constructor(dom::GlobalObject& aGlobal,
+                             const nsTArray<dom::OwningStringOrMatchPattern>& aPatterns,
+                             const MatchPatternOptions& aOptions,
+                             ErrorResult& aRv)
+{
+  ArrayType patterns;
+
+  for (auto& elem : aPatterns) {
+    if (elem.IsMatchPattern()) {
+      patterns.AppendElement(elem.GetAsMatchPattern());
+    } else {
+      RefPtr<MatchPattern> pattern = MatchPattern::Constructor(
+        aGlobal, elem.GetAsString(), aOptions, aRv);
+
+      if (!pattern) {
+        return nullptr;
+      }
+      patterns.AppendElement(Move(pattern));
+    }
+  }
+
+  RefPtr<MatchPatternSet> patternSet = new MatchPatternSet(aGlobal.GetAsSupports(),
+                                                           Move(patterns));
+  return patternSet.forget();
+}
+
+
+bool
+MatchPatternSet::Matches(const URLInfo& aURL, bool aExplicit) const
+{
+  for (const auto& pattern : mPatterns) {
+    if (pattern->Matches(aURL, aExplicit)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+MatchPatternSet::MatchesCookie(const CookieInfo& aCookie) const
+{
+  for (const auto& pattern : mPatterns) {
+    if (pattern->MatchesCookie(aCookie)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+MatchPatternSet::Subsumes(const MatchPattern& aPattern) const
+{
+  for (const auto& pattern : mPatterns) {
+    if (pattern->Subsumes(aPattern)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+MatchPatternSet::Overlaps(const MatchPatternSet& aPatternSet) const
+{
+  for (const auto& pattern : aPatternSet.mPatterns) {
+    if (Overlaps(*pattern)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool
+MatchPatternSet::Overlaps(const MatchPattern& aPattern) const
+{
+  for (const auto& pattern : mPatterns) {
+    if (pattern->Overlaps(aPattern)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool
+MatchPatternSet::OverlapsAll(const MatchPatternSet& aPatternSet) const
+{
+  for (const auto& pattern : aPatternSet.mPatterns) {
+    if (!Overlaps(*pattern)) {
+      return false;
+    }
+  }
+  return aPatternSet.mPatterns.Length() > 0;
+}
+
+
+JSObject*
+MatchPatternSet::WrapObject(JSContext* aCx, JS::HandleObject aGivenProto)
+{
+  return MatchPatternSetBinding::Wrap(aCx, this, aGivenProto);
+}
+
+
+NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE(MatchPatternSet, mPatterns, mParent)
+
+NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(MatchPatternSet)
+  NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
+  NS_INTERFACE_MAP_ENTRY(nsISupports)
+NS_INTERFACE_MAP_END
+
+NS_IMPL_CYCLE_COLLECTING_ADDREF(MatchPatternSet)
+NS_IMPL_CYCLE_COLLECTING_RELEASE(MatchPatternSet)
+
+
+/*****************************************************************************
+ * MatchGlob
+ *****************************************************************************/
+
+MatchGlob::~MatchGlob()
+{
+  mozilla::DropJSObjects(this);
+}
+
+/* static */ already_AddRefed<MatchGlob>
+MatchGlob::Constructor(dom::GlobalObject& aGlobal,
+                       const nsAString& aGlob,
+                       bool aAllowQuestion,
+                       ErrorResult& aRv)
+{
+  RefPtr<MatchGlob> glob = new MatchGlob(aGlobal.GetAsSupports());
+  glob->Init(aGlobal.Context(), aGlob, aAllowQuestion, aRv);
+  if (aRv.Failed()) {
+    return nullptr;
+  }
+  return glob.forget();
+}
+
+void
+MatchGlob::Init(JSContext* aCx, const nsAString& aGlob, bool aAllowQuestion, ErrorResult& aRv)
+{
+  mGlob = aGlob;
+
+  // Check for a literal match with no glob metacharacters.
+  auto index = mGlob.FindCharInSet(aAllowQuestion ? "*?" : "*");
+  if (index < 0) {
+    mPathLiteral = mGlob;
+    return;
+  }
+
+  // Check for a prefix match, where the only glob metacharacter is a "*"
+  // at the end of the string.
+  if (index == (int32_t)mGlob.Length() - 1 && mGlob[index] == '*') {
+    mPathLiteral = StringHead(mGlob, index);
+    mIsPrefix = true;
+    return;
+  }
+
+  // Fall back to the regexp slow path.
+  NS_NAMED_LITERAL_CSTRING(metaChars, ".+*?^${}()|[]\\");
+
+  nsAutoString escaped;
+  escaped.Append('^');
+
+  for (uint32_t i = 0; i < mGlob.Length(); i++) {
+    auto c = mGlob[i];
+    if (c == '*') {
+      escaped.AppendLiteral(".*");
+    } else if (c == '?' && aAllowQuestion) {
+      escaped.Append('.');
+    } else {
+      if (metaChars.Contains(c)) {
+        escaped.Append('\\');
+      }
+      escaped.Append(c);
+    }
+  }
+
+  escaped.Append('$');
+
+  // TODO: Switch to the Rust regexp crate, when Rust integration is easier.
+  // It uses a much more efficient, linear time matching algorithm, and
+  // doesn't require special casing for the literal and prefix cases.
+  mRegExp = JS_NewUCRegExpObject(aCx, escaped.get(), escaped.Length(), 0);
+  if (mRegExp) {
+    mozilla::HoldJSObjects(this);
+  } else {
+    aRv.NoteJSContextException(aCx);
+  }
+}
+
+bool
+MatchGlob::Matches(const nsAString& aString) const
+{
+  if (mRegExp) {
+    AutoJSAPI jsapi;
+    jsapi.Init();
+    JSContext* cx = jsapi.cx();
+
+    JSAutoCompartment ac(cx, mRegExp);
+
+    JS::RootedObject regexp(cx, mRegExp);
+    JS::RootedValue result(cx);
+
+    nsString input(aString);
+
+    size_t index = 0;
+    if (!JS_ExecuteRegExpNoStatics(cx, regexp, input.BeginWriting(), aString.Length(),
+                                   &index, true, &result)) {
+      return false;
+    }
+
+    return result.isBoolean() && result.toBoolean();
+  }
+
+  if (mIsPrefix) {
+    return mPathLiteral == StringHead(aString, mPathLiteral.Length());
+  }
+
+  return mPathLiteral == aString;
+}
+
+
+JSObject*
+MatchGlob::WrapObject(JSContext* aCx, JS::HandleObject aGivenProto)
+{
+  return MatchGlobBinding::Wrap(aCx, this, aGivenProto);
+}
+
+
+NS_IMPL_CYCLE_COLLECTION_CLASS(MatchGlob)
+
+NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(MatchGlob)
+  NS_IMPL_CYCLE_COLLECTION_UNLINK_PRESERVED_WRAPPER
+  NS_IMPL_CYCLE_COLLECTION_UNLINK(mParent)
+  tmp->mRegExp = nullptr;
+NS_IMPL_CYCLE_COLLECTION_UNLINK_END
+
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(MatchGlob)
+  NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mParent)
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
+
+NS_IMPL_CYCLE_COLLECTION_TRACE_BEGIN(MatchGlob)
+  NS_IMPL_CYCLE_COLLECTION_TRACE_PRESERVED_WRAPPER
+  NS_IMPL_CYCLE_COLLECTION_TRACE_JS_MEMBER_CALLBACK(mRegExp)
+NS_IMPL_CYCLE_COLLECTION_TRACE_END
+
+NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(MatchGlob)
+  NS_WRAPPERCACHE_INTERFACE_MAP_ENTRY
+  NS_INTERFACE_MAP_ENTRY(nsISupports)
+NS_INTERFACE_MAP_END
+
+NS_IMPL_CYCLE_COLLECTING_ADDREF(MatchGlob)
+NS_IMPL_CYCLE_COLLECTING_RELEASE(MatchGlob)
+
+
+/*****************************************************************************
+ * MatchGlobSet
+ *****************************************************************************/
+
+bool
+MatchGlobSet::Matches(const nsAString& aValue) const
+{
+  for (auto& glob : *this) {
+    if (glob->Matches(aValue)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+} // namespace extensions
+} // namespace mozilla
+
new file mode 100644
--- /dev/null
+++ b/toolkit/components/extensions/MatchPattern.h
@@ -0,0 +1,326 @@
+/* -*-  Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_extensions_MatchPattern_h
+#define mozilla_extensions_MatchPattern_h
+
+#include "mozilla/dom/BindingDeclarations.h"
+#include "mozilla/dom/MatchPatternBinding.h"
+#include "mozilla/extensions/MatchGlob.h"
+
+#include "jspubtd.h"
+
+#include "mozilla/ClearOnShutdown.h"
+#include "mozilla/Likely.h"
+#include "mozilla/Maybe.h"
+#include "mozilla/RefCounted.h"
+#include "nsCOMPtr.h"
+#include "nsCycleCollectionParticipant.h"
+#include "nsTArray.h"
+#include "nsIAtom.h"
+#include "nsICookie2.h"
+#include "nsISupports.h"
+#include "nsIURI.h"
+#include "nsWrapperCache.h"
+
+
+namespace mozilla {
+namespace extensions {
+
+using dom::MatchPatternOptions;
+
+
+// A sorted, binary-search-backed set of atoms, optimized for frequent lookups
+// and infrequent updates.
+class AtomSet final : public RefCounted<AtomSet>
+{
+  using ArrayType = AutoTArray<RefPtr<nsIAtom>, 1>;
+
+public:
+  MOZ_DECLARE_REFCOUNTED_TYPENAME(AtomSet)
+
+  explicit AtomSet(const nsTArray<nsString>& aElems);
+
+  explicit AtomSet(const char** aElems);
+
+  MOZ_IMPLICIT AtomSet(std::initializer_list<nsIAtom*> aIL);
+
+  bool Contains(const nsAString& elem) const
+  {
+    nsCOMPtr<nsIAtom> atom = NS_AtomizeMainThread(elem);
+    return Contains(atom);
+  }
+
+  bool Contains(const nsACString& aElem) const
+  {
+    nsCOMPtr<nsIAtom> atom = NS_Atomize(aElem);
+    return Contains(atom);
+  }
+
+  bool Contains(const nsIAtom* aAtom) const
+  {
+    return mElems.BinaryIndexOf(aAtom) != mElems.NoIndex;
+  }
+
+  bool Intersects(const AtomSet& aOther) const;
+
+
+  void Add(nsIAtom* aElem);
+  void Remove(nsIAtom* aElem);
+
+  void Add(const nsAString& aElem)
+  {
+    nsCOMPtr<nsIAtom> atom = NS_AtomizeMainThread(aElem);
+    return Add(atom);
+  }
+
+  void Remove(const nsAString& aElem)
+  {
+    nsCOMPtr<nsIAtom> atom = NS_AtomizeMainThread(aElem);
+    return Remove(atom);
+  }
+
+  // Returns a cached, statically-allocated matcher for the given set of
+  // literal strings.
+  template <const char** schemes>
+  static already_AddRefed<AtomSet>
+  Get()
+  {
+    static RefPtr<AtomSet> sMatcher;
+
+    if (MOZ_UNLIKELY(!sMatcher)) {
+      sMatcher = new AtomSet(schemes);
+      ClearOnShutdown(&sMatcher);
+    }
+
+    return do_AddRef(sMatcher);
+  }
+
+  void
+  Get(nsTArray<nsString>& aResult) const
+  {
+    aResult.SetCapacity(mElems.Length());
+
+    for (const auto& atom : mElems) {
+      aResult.AppendElement(nsDependentAtomString(atom));
+    }
+  }
+
+  auto begin() const
+    -> decltype(DeclVal<const ArrayType>().begin())
+  {
+    return mElems.begin();
+  }
+
+  auto end() const
+    -> decltype(DeclVal<const ArrayType>().end())
+  {
+    return mElems.end();
+  }
+
+private:
+  ArrayType mElems;
+
+  void SortAndUniquify();
+};
+
+
+// A helper class to lazily retrieve, transcode, and atomize certain URI
+// properties the first time they're used, and cache the results, so that they
+// can be used across multiple match operations.
+class MOZ_STACK_CLASS URLInfo final
+{
+public:
+  MOZ_IMPLICIT URLInfo(nsIURI* aURI)
+    : mURI(aURI)
+  {
+    mHost.SetIsVoid(true);
+  }
+
+  URLInfo(const URLInfo& aOther)
+    : URLInfo(aOther.mURI.get())
+  {}
+
+  nsIURI* URI() const { return mURI; }
+
+  nsIAtom* Scheme() const;
+  const nsCString& Host() const;
+  const nsString& Path() const;
+  const nsString& FilePath() const;
+  const nsString& Spec() const;
+
+  bool InheritsPrincipal() const;
+
+private:
+  nsIURI* URINoRef() const;
+
+  nsCOMPtr<nsIURI> mURI;
+  mutable nsCOMPtr<nsIURI> mURINoRef;
+
+  mutable nsCOMPtr<nsIAtom> mScheme;
+  mutable nsCString mHost;
+
+  mutable nsAutoString mPath;
+  mutable nsAutoString mFilePath;
+  mutable nsAutoString mSpec;
+
+  mutable Maybe<bool> mInheritsPrincipal;
+};
+
+
+// Similar to URLInfo, but for cookies.
+class MOZ_STACK_CLASS CookieInfo final
+{
+public:
+  MOZ_IMPLICIT CookieInfo(nsICookie2* aCookie)
+    : mCookie(aCookie)
+  {}
+
+  bool IsSecure() const;
+  bool IsDomain() const;
+
+  const nsCString& Host() const;
+  const nsCString& RawHost() const;
+
+private:
+  nsCOMPtr<nsICookie2> mCookie;
+
+  mutable Maybe<bool> mIsSecure;
+  mutable Maybe<bool> mIsDomain;
+
+  mutable nsCString mHost;
+  mutable nsCString mRawHost;
+};
+
+
+class MatchPattern final : public nsISupports
+                         , public nsWrapperCache
+{
+  NS_DECL_CYCLE_COLLECTING_ISUPPORTS
+  NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS(MatchPattern)
+
+  static already_AddRefed<MatchPattern>
+  Constructor(dom::GlobalObject& aGlobal,
+              const nsAString& aPattern,
+              const MatchPatternOptions& aOptions,
+              ErrorResult& aRv);
+
+  bool Matches(const URLInfo& aURL, bool aExplicit = false) const;
+
+  bool MatchesCookie(const CookieInfo& aCookie) const;
+
+  bool MatchesDomain(const nsACString& aDomain) const;
+
+  bool Subsumes(const MatchPattern& aPattern) const;
+
+  bool Overlaps(const MatchPattern& aPattern) const;
+
+  bool DomainIsWildcard() const
+  {
+    return mMatchSubdomain && mDomain.IsEmpty();
+  }
+
+  void GetPattern(nsAString& aPattern) const
+  {
+    aPattern = mPattern;
+  }
+
+  nsISupports* GetParentObject() const { return mParent; }
+
+  virtual JSObject* WrapObject(JSContext* aCx, JS::HandleObject aGivenProto) override;
+
+protected:
+  virtual ~MatchPattern() = default;
+
+private:
+  explicit MatchPattern(nsISupports* aParent) : mParent(aParent) {}
+
+  void Init(JSContext* aCx, const nsAString& aPattern, bool aIgnorePath, ErrorResult& aRv);
+
+  bool SubsumesDomain(const MatchPattern& aPattern) const;
+
+
+  nsCOMPtr<nsISupports> mParent;
+
+  // The normalized match pattern string that this object represents.
+  nsString mPattern;
+
+  // The set of atomized URI schemes that this pattern matches.
+  RefPtr<AtomSet> mSchemes;
+
+  // The domain that this matcher matches. If mMatchSubdomain is false, only
+  // matches the exact domain. If it's true, matches the domain or any
+  // subdomain.
+  //
+  // For instance, "*.foo.com" gives mDomain = "foo.com" and mMatchSubdomain = true,
+  // and matches "foo.com" or "bar.foo.com" but not "barfoo.com".
+  //
+  // While "foo.com" gives mDomain = "foo.com" and mMatchSubdomain = false,
+  // and matches "foo.com" but not "bar.foo.com".
+  nsCString mDomain;
+  bool mMatchSubdomain = false;
+
+  // The glob against which the URL path must match. If null, the path is
+  // ignored entirely. If non-null, the path must match this glob.
+  RefPtr<MatchGlob> mPath;
+};
+
+
+class MatchPatternSet final : public nsISupports
+                            , public nsWrapperCache
+{
+  NS_DECL_CYCLE_COLLECTING_ISUPPORTS
+  NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS(MatchPatternSet)
+
+  using ArrayType = nsTArray<RefPtr<MatchPattern>>;
+
+
+  static already_AddRefed<MatchPatternSet>
+  Constructor(dom::GlobalObject& aGlobal,
+              const nsTArray<dom::OwningStringOrMatchPattern>& aPatterns,
+              const MatchPatternOptions& aOptions,
+              ErrorResult& aRv);
+
+
+  bool Matches(const URLInfo& aURL, bool aExplicit = false) const;
+
+  bool MatchesCookie(const CookieInfo& aCookie) const;
+
+  bool Subsumes(const MatchPattern& aPattern) const;
+
+  bool Overlaps(const MatchPattern& aPattern) const;
+
+  bool Overlaps(const MatchPatternSet& aPatternSet) const;
+
+  bool OverlapsAll(const MatchPatternSet& aPatternSet) const;
+
+  void GetPatterns(ArrayType& aPatterns)
+  {
+    aPatterns.AppendElements(mPatterns);
+  }
+
+
+  nsISupports* GetParentObject() const { return mParent; }
+
+  virtual JSObject* WrapObject(JSContext* aCx, JS::HandleObject aGivenProto) override;
+
+protected:
+  virtual ~MatchPatternSet() = default;
+
+private:
+  explicit MatchPatternSet(nsISupports* aParent, ArrayType&& aPatterns)
+    : mParent(aParent)
+    , mPatterns(Forward<ArrayType>(aPatterns))
+  {}
+
+  nsCOMPtr<nsISupports> mParent;
+
+  ArrayType mPatterns;
+};
+
+} // namespace extensions
+} // namespace mozilla
+
+#endif // mozilla_extensions_MatchPattern_h
--- a/toolkit/components/extensions/moz.build
+++ b/toolkit/components/extensions/moz.build
@@ -40,16 +40,28 @@ TESTING_JS_MODULES += [
     'ExtensionXPCShellUtils.jsm',
 ]
 
 DIRS += [
     'schemas',
     'webrequest',
 ]
 
+EXPORTS.mozilla.extensions = [
+    'MatchGlob.h',
+    'MatchPattern.h',
+]
+
+UNIFIED_SOURCES += [
+    'MatchPattern.cpp',
+]
+
+FINAL_LIBRARY = 'xul'
+
+
 JAR_MANIFESTS += ['jar.mn']
 
 BROWSER_CHROME_MANIFESTS += [
     'test/browser/browser.ini',
 ]
 
 MOCHITEST_MANIFESTS += [
     'test/mochitest/mochitest-remote.ini',
copy from toolkit/modules/tests/xpcshell/test_MatchPattern.js
copy to toolkit/components/extensions/test/xpcshell/test_MatchPattern.js
--- a/toolkit/modules/tests/xpcshell/test_MatchPattern.js
+++ b/toolkit/components/extensions/test/xpcshell/test_MatchPattern.js
@@ -1,51 +1,74 @@
-/* Any copyright is dedicated to the Public Domain.
-   http://creativecommons.org/publicdomain/zero/1.0/ */
-
+/* -*- Mode: indent-tabs-mode: nil; js-indent-level: 2 -*- */
+/* vim: set sts=2 sw=2 et tw=80: */
 "use strict";
 
-Components.utils.import("resource://gre/modules/MatchPattern.jsm");
-Components.utils.import("resource://gre/modules/Services.jsm");
+add_task(async function test_MatchPattern_matches() {
+  function test(url, pattern, normalized = pattern) {
+    let uri = Services.io.newURI(url);
+
+    pattern = Array.concat(pattern);
+    normalized = Array.concat(normalized);
+
+    let patterns = pattern.map(pat => new MatchPattern(pat));
+
+    let set = new MatchPatternSet(pattern);
+    let set2 = new MatchPatternSet(patterns);
 
-function test_matches() {
-  function test(url, pattern) {
-    let uri = Services.io.newURI(url);
-    let m = new MatchPattern(pattern);
-    return m.matches(uri);
+    deepEqual(set2.patterns, patterns, "Patterns in set should equal the input patterns");
+
+    equal(set.matches(uri), set2.matches(uri), "Single pattern and pattern set should return the same match");
+
+    for (let [i, pat] of patterns.entries()) {
+      equal(pat.pattern, normalized[i], "Pattern property should contain correct normalized pattern value");
+    }
+
+    if (patterns.length == 1) {
+      equal(patterns[0].matches(uri), set.matches(uri), "Single pattern and string set should return the same match");
+    }
+
+    return set.matches(uri);
   }
 
-  function pass({url, pattern}) {
-    do_check_true(test(url, pattern), `Expected match: ${JSON.stringify(pattern)}, ${url}`);
+  function pass({url, pattern, normalized}) {
+    ok(test(url, pattern, normalized), `Expected match: ${JSON.stringify(pattern)}, ${url}`);
   }
 
-  function fail({url, pattern}) {
-    do_check_false(test(url, pattern), `Expected no match: ${JSON.stringify(pattern)}, ${url}`);
+  function fail({url, pattern, normalized}) {
+    ok(!test(url, pattern, normalized), `Expected no match: ${JSON.stringify(pattern)}, ${url}`);
+  }
+
+  function invalid({pattern}) {
+    Assert.throws(() => new MatchPattern(pattern), /.*/,
+                  `Invalid pattern '${pattern}' should throw`);
+    Assert.throws(() => new MatchPatternSet([pattern]), /.*/,
+                  `Invalid pattern '${pattern}' should throw`);
   }
 
   // Invalid pattern.
-  fail({url: "http://mozilla.org", pattern: ""});
+  invalid({pattern: ""});
 
   // Pattern must include trailing slash.
-  fail({url: "http://mozilla.org", pattern: "http://mozilla.org"});
+  invalid({pattern: "http://mozilla.org"});
 
   // Protocol not allowed.
-  fail({url: "http://mozilla.org", pattern: "gopher://wuarchive.wustl.edu/"});
+  invalid({pattern: "gopher://wuarchive.wustl.edu/"});
 
   pass({url: "http://mozilla.org", pattern: "http://mozilla.org/"});
   pass({url: "http://mozilla.org/", pattern: "http://mozilla.org/"});
 
   pass({url: "http://mozilla.org/", pattern: "*://mozilla.org/"});
   pass({url: "https://mozilla.org/", pattern: "*://mozilla.org/"});
   fail({url: "file://mozilla.org/", pattern: "*://mozilla.org/"});
   fail({url: "ftp://mozilla.org/", pattern: "*://mozilla.org/"});
 
   fail({url: "http://mozilla.com", pattern: "http://*mozilla.com*/"});
   fail({url: "http://mozilla.com", pattern: "http://mozilla.*/"});
-  fail({url: "http://mozilla.com", pattern: "http:/mozilla.com/"});
+  invalid({pattern: "http:/mozilla.com/"});
 
   pass({url: "http://google.com", pattern: "http://*.google.com/"});
   pass({url: "http://docs.google.com", pattern: "http://*.google.com/"});
 
   pass({url: "http://mozilla.org:8080", pattern: "http://mozilla.org/"});
   pass({url: "http://mozilla.org:8080", pattern: "*://mozilla.org/"});
   fail({url: "http://mozilla.org:8080", pattern: "http://mozilla.org:8080/"});
 
@@ -65,17 +88,17 @@ function test_matches() {
   fail({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/"});
   pass({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/*"});
   pass({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/a*f"});
   pass({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/a*"});
   pass({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/*f"});
   fail({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/*e"});
   fail({url: "http://mozilla.com/abc/def", pattern: "http://mozilla.com/*c"});
 
-  fail({url: "http:///a.html", pattern: "http:///a.html"});
+  invalid({pattern: "http:///a.html"});
   pass({url: "file:///foo", pattern: "file:///foo*"});
   pass({url: "file:///foo/bar.html", pattern: "file:///foo*"});
 
   pass({url: "http://mozilla.org/a", pattern: "<all_urls>"});
   pass({url: "https://mozilla.org/a", pattern: "<all_urls>"});
   pass({url: "ftp://mozilla.org/a", pattern: "<all_urls>"});
   pass({url: "file:///a", pattern: "<all_urls>"});
   fail({url: "gopher://wuarchive.wustl.edu/a", pattern: "<all_urls>"});
@@ -83,22 +106,27 @@ function test_matches() {
   // Multiple patterns.
   pass({url: "http://mozilla.org", pattern: ["http://mozilla.org/"]});
   pass({url: "http://mozilla.org", pattern: ["http://mozilla.org/", "http://mozilla.com/"]});
   pass({url: "http://mozilla.com", pattern: ["http://mozilla.org/", "http://mozilla.com/"]});
   fail({url: "http://mozilla.biz", pattern: ["http://mozilla.org/", "http://mozilla.com/"]});
 
   // Match url with fragments.
   pass({url: "http://mozilla.org/base#some-fragment", pattern: "http://mozilla.org/base"});
-}
+});
 
-function test_overlaps() {
+add_task(async function test_MatchPattern_overlaps() {
   function test(filter, hosts, optional) {
-    const f = new MatchPattern(filter);
-    return f.overlapsPermissions(new MatchPattern(hosts), new MatchPattern(optional));
+    filter = Array.concat(filter);
+    hosts = Array.concat(hosts);
+    optional = Array.concat(optional);
+
+    const set = new MatchPatternSet([...hosts, ...optional]);
+    const pat = new MatchPatternSet(filter);
+    return set.overlapsAll(pat);
   }
 
   function pass({filter = [], hosts = [], optional = []}) {
     ok(test(filter, hosts, optional), `Expected overlap: ${filter}, ${hosts} (${optional})`);
   }
 
   function fail({filter = [], hosts = [], optional = []}) {
     ok(!test(filter, hosts, optional), `Expected no overlap: ${filter}, ${hosts} (${optional})`);
@@ -127,17 +155,16 @@ function test_overlaps() {
   fail({hosts: "http://*.ab.cd/", filter: "http://*.fake-ab.cd/"});
 
   // Wildcard domain.
   pass({hosts: "http://*/", filter: "http://ab.cd/"});
   fail({hosts: "http://*/", filter: "https://ab.cd/"});
 
   // Wildcard wildcards.
   pass({hosts: "<all_urls>", filter: "ftp://ab.cd/"});
-  fail({hosts: "<all_urls>", filter: ""});
   fail({hosts: "<all_urls>"});
 
   // Multiple hosts.
   pass({hosts: ["http://ab.cd/"], filter: ["http://ab.cd/"]});
   pass({hosts: ["http://ab.cd/", "http://ab.xy/"], filter: "http://ab.cd/"});
   pass({hosts: ["http://ab.cd/", "http://ab.xy/"], filter: "http://ab.xy/"});
   fail({hosts: ["http://ab.cd/", "http://ab.xy/"], filter: "http://ab.zz/"});
 
@@ -145,14 +172,57 @@ function test_overlaps() {
   pass({hosts: ["http://*.ab.cd/"], filter: ["http://ab.cd/", "http://www.ab.cd/"]});
   pass({hosts: ["http://ab.cd/", "http://ab.xy/"], filter: ["http://ab.cd/", "http://ab.xy/"]});
   fail({hosts: ["http://ab.cd/", "http://ab.xy/"], filter: ["http://ab.cd/", "http://ab.zz/"]});
 
   // Optional.
   pass({hosts: [], optional: "http://ab.cd/", filter: "http://ab.cd/"});
   pass({hosts: "http://ab.cd/", optional: "http://ab.xy/", filter: ["http://ab.cd/", "http://ab.xy/"]});
   fail({hosts: "http://ab.cd/", optional: "https://ab.xy/", filter: "http://ab.xy/"});
-}
+});
+
+add_task(async function test_MatchGlob() {
+  function test(url, pattern) {
+    let m = new MatchGlob(pattern[0]);
+    return m.matches(Services.io.newURI(url).spec);
+  }
+
+  function pass({url, pattern}) {
+    ok(test(url, pattern), `Expected match: ${JSON.stringify(pattern)}, ${url}`);
+  }
+
+  function fail({url, pattern}) {
+    ok(!test(url, pattern), `Expected no match: ${JSON.stringify(pattern)}, ${url}`);
+  }
+
+  let moz = "http://mozilla.org";
+
+  pass({url: moz, pattern: ["*"]});
+  pass({url: moz, pattern: ["http://*"]});
+  pass({url: moz, pattern: ["*mozilla*"]});
+  // pass({url: moz, pattern: ["*example*", "*mozilla*"]});
 
-function run_test() {
-  test_matches();
-  test_overlaps();
-}
+  pass({url: moz, pattern: ["*://*"]});
+  pass({url: "https://mozilla.org", pattern: ["*://*"]});
+
+  // Documentation example
+  pass({url: "http://www.example.com/foo/bar", pattern: ["http://???.example.com/foo/*"]});
+  pass({url: "http://the.example.com/foo/", pattern: ["http://???.example.com/foo/*"]});
+  fail({url: "http://my.example.com/foo/bar", pattern: ["http://???.example.com/foo/*"]});
+  fail({url: "http://example.com/foo/", pattern: ["http://???.example.com/foo/*"]});
+  fail({url: "http://www.example.com/foo", pattern: ["http://???.example.com/foo/*"]});
+
+  // Matches path
+  let path = moz + "/abc/def";
+  pass({url: path, pattern: ["*def"]});
+  pass({url: path, pattern: ["*c/d*"]});
+  pass({url: path, pattern: ["*org/abc*"]});
+  fail({url: path + "/", pattern: ["*def"]});
+
+  // Trailing slash
+  pass({url: moz, pattern: ["*.org/"]});
+  fail({url: moz, pattern: ["*.org"]});
+
+  // Wrong TLD
+  fail({url: moz, pattern: ["*oz*.com/"]});
+  // Case sensitive
+  fail({url: moz, pattern: ["*.ORG/"]});
+});
--- a/toolkit/components/extensions/test/xpcshell/xpcshell.ini
+++ b/toolkit/components/extensions/test/xpcshell/xpcshell.ini
@@ -4,16 +4,18 @@ firefox-appdir = browser
 skip-if = appname == "thunderbird"
 dupe-manifest =
 support-files =
   data/**
   head_sync.js
   xpcshell-content.ini
 tags = webextensions
 
+[test_MatchPattern.js]
+
 [test_csp_custom_policies.js]
 [test_csp_validator.js]
 [test_ext_alarms.js]
 [test_ext_alarms_does_not_fire.js]
 [test_ext_alarms_periodic.js]
 [test_ext_alarms_replaces.js]
 [test_ext_api_permissions.js]
 [test_ext_background_generated_load_events.js]