--- a/dom/xbl/nsXBLWindowKeyHandler.cpp
+++ b/dom/xbl/nsXBLWindowKeyHandler.cpp
@@ -20,27 +20,31 @@
 #include "nsNetUtil.h"
 #include "nsContentUtils.h"
 #include "nsXBLPrototypeBinding.h"
 #include "nsPIDOMWindow.h"
 #include "nsIDocShell.h"
 #include "nsIPresShell.h"
 #include "mozilla/EventListenerManager.h"
 #include "mozilla/EventStateManager.h"
+#include "mozilla/Move.h"
 #include "nsISelectionController.h"
 #include "mozilla/Preferences.h"
+#include "mozilla/StaticPtr.h"
 #include "mozilla/TextEvents.h"
 #include "mozilla/dom/Element.h"
 #include "mozilla/dom/Event.h"
+#include "mozilla/layers/Keyboard.h"
 #include "nsIEditor.h"
 #include "nsIHTMLEditor.h"
 #include "nsIDOMDocument.h"
 
 using namespace mozilla;
 using namespace mozilla::dom;
+using namespace mozilla::layers;
 
 class nsXBLSpecialDocInfo : public nsIObserver
 {
 public:
   RefPtr<nsXBLDocumentInfo> mHTMLBindings;
   RefPtr<nsXBLDocumentInfo> mUserHTMLBindings;
 
   static const char sHTMLBindingStr[];
@@ -141,19 +145,28 @@ nsXBLSpecialDocInfo::GetAllHandlers(cons
     GetHandlers(mUserHTMLBindings, type, aUserHandler);
   }
   if (mHTMLBindings) {
     GetHandlers(mHTMLBindings, nsDependentCString(aType), aHandler);
   }
 }
 
 // Init statics
-nsXBLSpecialDocInfo* nsXBLWindowKeyHandler::sXBLSpecialDocInfo = nullptr;
+static StaticRefPtr<nsXBLSpecialDocInfo> sXBLSpecialDocInfo;
 uint32_t nsXBLWindowKeyHandler::sRefCnt = 0;
 
+/* static */ void
+nsXBLWindowKeyHandler::EnsureSpecialDocInfo()
+{
+  if (!sXBLSpecialDocInfo) {
+    sXBLSpecialDocInfo = new nsXBLSpecialDocInfo();
+  }
+  sXBLSpecialDocInfo->LoadDocInfo();
+}
+
 nsXBLWindowKeyHandler::nsXBLWindowKeyHandler(nsIDOMElement* aElement,
                                              EventTarget* aTarget)
   : mTarget(aTarget),
     mHandler(nullptr),
     mUserHandler(nullptr)
 {
   mWeakPtrForElement = do_GetWeakReference(aElement);
   ++sRefCnt;
@@ -162,17 +175,17 @@ nsXBLWindowKeyHandler::nsXBLWindowKeyHan
 nsXBLWindowKeyHandler::~nsXBLWindowKeyHandler()
 {
   // If mWeakPtrForElement is non-null, we created a prototype handler.
   if (mWeakPtrForElement)
     delete mHandler;
 
   --sRefCnt;
   if (!sRefCnt) {
-    NS_IF_RELEASE(sXBLSpecialDocInfo);
+    sXBLSpecialDocInfo = nullptr;
   }
 }
 
 NS_IMPL_ISUPPORTS(nsXBLWindowKeyHandler,
                   nsIDOMEventListener)
 
 static void
 BuildHandlerChain(nsIContent* aContent, nsXBLPrototypeHandler** aResult)
@@ -223,21 +236,17 @@ nsXBLWindowKeyHandler::EnsureHandlers()
   if (el) {
     // We are actually a XUL <keyset>.
     if (mHandler)
       return NS_OK;
 
     nsCOMPtr<nsIContent> content(do_QueryInterface(el));
     BuildHandlerChain(content, &mHandler);
   } else { // We are an XBL file of handlers.
-    if (!sXBLSpecialDocInfo) {
-      sXBLSpecialDocInfo = new nsXBLSpecialDocInfo();
-      NS_ADDREF(sXBLSpecialDocInfo);
-    }
-    sXBLSpecialDocInfo->LoadDocInfo();
+    EnsureSpecialDocInfo();
 
     // Now determine which handlers we should be using.
     if (IsHTMLEditableFieldFocused()) {
       sXBLSpecialDocInfo->GetAllHandlers("editor", &mHandler, &mUserHandler);
     }
     else {
       sXBLSpecialDocInfo->GetAllHandlers("browser", &mHandler, &mUserHandler);
     }
@@ -392,16 +401,51 @@ nsXBLWindowKeyHandler::RemoveKeyboardEve
   aEventListenerManager->RemoveEventListenerByType(
                            this, NS_LITERAL_STRING("mozkeydownonplugin"),
                            TrustedEventsAtSystemGroupBubble());
   aEventListenerManager->RemoveEventListenerByType(
                            this, NS_LITERAL_STRING("mozkeyuponplugin"),
                            TrustedEventsAtSystemGroupBubble());
 }
 
+/* static */ KeyboardMap
+nsXBLWindowKeyHandler::CollectKeyboardShortcuts()
+{
+  // Load the XBL handlers
+  EnsureSpecialDocInfo();
+
+  nsXBLPrototypeHandler* handlers = nullptr;
+  nsXBLPrototypeHandler* userHandlers = nullptr;
+  sXBLSpecialDocInfo->GetAllHandlers("browser", &handlers, &userHandlers);
+
+  // Convert the handlers into keyboard shortcuts, using an AutoTArray with
+  // the maximum amount of shortcuts used on any platform to minimize allocations
+  AutoTArray<KeyboardShortcut, 46> shortcuts;
+
+  for (nsXBLPrototypeHandler* handler = handlers;
+       handler;
+       handler = handler->GetNextHandler()) {
+    KeyboardShortcut shortcut;
+    if (handler->TryConvertToKeyboardShortcut(&shortcut)) {
+      shortcuts.AppendElement(shortcut);
+    }
+  }
+
+  for (nsXBLPrototypeHandler* handler = userHandlers;
+       handler;
+       handler = handler->GetNextHandler()) {
+    KeyboardShortcut shortcut;
+    if (handler->TryConvertToKeyboardShortcut(&shortcut)) {
+      shortcuts.AppendElement(shortcut);
+    }
+  }
+
+  return KeyboardMap(mozilla::Move(shortcuts));
+}
+
 nsIAtom*
 nsXBLWindowKeyHandler::ConvertEventToDOMEventType(
                          const WidgetKeyboardEvent& aWidgetKeyboardEvent) const
 {
   if (aWidgetKeyboardEvent.IsKeyDownOrKeyDownOnPlugin()) {
     return nsGkAtoms::keydown;
   }
   if (aWidgetKeyboardEvent.IsKeyUpOrKeyUpOnPlugin()) {

--- a/dom/xbl/nsXBLWindowKeyHandler.h
+++ b/dom/xbl/nsXBLWindowKeyHandler.h
@@ -3,47 +3,50 @@
 /* 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 nsXBLWindowKeyHandler_h__
 #define nsXBLWindowKeyHandler_h__
 
 #include "mozilla/EventForwards.h"
+#include "mozilla/layers/Keyboard.h"
 #include "nsWeakPtr.h"
 #include "nsIDOMEventListener.h"
 
 class nsIAtom;
 class nsIDOMElement;
 class nsIDOMKeyEvent;
-class nsXBLSpecialDocInfo;
 class nsXBLPrototypeHandler;
 
 namespace mozilla {
 class EventListenerManager;
 struct IgnoreModifierState;
 namespace dom {
 class Element;
 class EventTarget;
 } // namespace dom
 } // namespace mozilla
 
 class nsXBLWindowKeyHandler : public nsIDOMEventListener
 {
   typedef mozilla::EventListenerManager EventListenerManager;
   typedef mozilla::IgnoreModifierState IgnoreModifierState;
+  typedef mozilla::layers::KeyboardMap KeyboardMap;
 
 public:
   nsXBLWindowKeyHandler(nsIDOMElement* aElement, mozilla::dom::EventTarget* aTarget);
 
   void InstallKeyboardEventListenersTo(
          EventListenerManager* aEventListenerManager);
   void RemoveKeyboardEventListenersFrom(
          EventListenerManager* aEventListenerManager);
 
+  static KeyboardMap CollectKeyboardShortcuts();
+
   NS_DECL_ISUPPORTS
   NS_DECL_NSIDOMEVENTLISTENER
 
 protected:
   virtual ~nsXBLWindowKeyHandler();
 
   nsresult WalkHandlers(nsIDOMKeyEvent* aKeyEvent, nsIAtom* aEventType);
 
@@ -75,16 +78,19 @@ protected:
                           bool* aOutReservedForChrome = nullptr);
 
   // Returns event type for matching between aWidgetKeyboardEvent and
   // shortcut key handlers.  This is used for calling WalkHandlers(),
   // WalkHandlersInternal() and WalkHandlersAndExecute().
   nsIAtom* ConvertEventToDOMEventType(
              const mozilla::WidgetKeyboardEvent& aWidgetKeyboardEvent) const;
 
+  // lazily load the special doc info for loading handlers
+  static void EnsureSpecialDocInfo();
+
   // lazily load the handlers. Overridden to handle being attached
   // to a particular element rather than the document
   nsresult EnsureHandlers();
 
   // Is an HTML editable element focused
   bool IsHTMLEditableFieldFocused();
 
   // Returns the element which was passed as a parameter to the constructor,
@@ -115,18 +121,17 @@ protected:
   nsWeakPtr              mWeakPtrForElement;
   mozilla::dom::EventTarget* mTarget; // weak ref
 
   // these are not owning references; the prototype handlers are owned
   // by the prototype bindings which are owned by the docinfo.
   nsXBLPrototypeHandler* mHandler;     // platform bindings
   nsXBLPrototypeHandler* mUserHandler; // user-specific bindings
 
-  // holds document info about bindings
-  static nsXBLSpecialDocInfo* sXBLSpecialDocInfo;
+  // holds reference count to document info about bindings
   static uint32_t sRefCnt;
 };
 
 already_AddRefed<nsXBLWindowKeyHandler>
 NS_NewXBLWindowKeyHandler(nsIDOMElement* aElement,
                           mozilla::dom::EventTarget* aTarget);
 
 #endif

--- a/gfx/layers/apz/src/Keyboard.cpp
+++ b/gfx/layers/apz/src/Keyboard.cpp
@@ -1,16 +1,16 @@
 /* -*- Mode: C++; tab-width: 8; 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/layers/Keyboard.h"
 
-#include "mozilla/TextEvents.h" // for IgnoreModifierState
+#include "mozilla/TextEvents.h" // for IgnoreModifierState, ShortcutKeyCandidate
 
 namespace mozilla {
 namespace layers {
 
 /* static */ nsIScrollableFrame::ScrollUnit
 KeyboardScrollAction::GetScrollUnit(KeyboardScrollAction::KeyboardScrollActionType aDeltaType)
 {
   switch (aDeltaType) {
@@ -125,10 +125,67 @@ KeyboardShortcut::MatchesModifiers(const
   if (aIgnore.mShift) {
     modifiersMask &= ~MODIFIER_SHIFT;
   }
 
   // Mask off the modifiers we are ignoring from the keyboard input
   return (aInput.modifiers & modifiersMask) == mModifiers;
 }
 
+KeyboardMap::KeyboardMap(nsTArray<KeyboardShortcut>&& aShortcuts)
+  : mShortcuts(aShortcuts)
+{
+}
+
+KeyboardMap::KeyboardMap()
+{
+}
+
+Maybe<KeyboardShortcut>
+KeyboardMap::FindMatch(const KeyboardInput& aEvent) const
+{
+  // If there are no shortcut candidates, then just search with with the
+  // keyboard input
+  if (aEvent.mShortcutCandidates.IsEmpty()) {
+    return FindMatchInternal(aEvent, IgnoreModifierState());
+  }
+
+  // Otherwise do a search with each shortcut candidate in order
+  for (auto& key : aEvent.mShortcutCandidates) {
+    IgnoreModifierState ignoreModifierState;
+    ignoreModifierState.mShift = key.mIgnoreShift;
+
+    auto match = FindMatchInternal(aEvent, ignoreModifierState, key.mCharCode);
+    if (match) {
+      return match;
+    }
+  }
+  return Nothing();
+}
+
+Maybe<KeyboardShortcut>
+KeyboardMap::FindMatchInternal(const KeyboardInput& aEvent,
+                               const IgnoreModifierState& aIgnore,
+                               uint32_t aOverrideCharCode) const
+{
+  for (auto& shortcut : mShortcuts) {
+    if (shortcut.Matches(aEvent, aIgnore, aOverrideCharCode)) {
+      return Some(shortcut);
+    }
+  }
+
+#ifdef XP_WIN
+  // Windows native applications ignore Windows-Logo key state when checking
+  // shortcut keys even if the key is pressed.  Therefore, if there is no
+  // shortcut key which exactly matches current modifier state, we should
+  // retry to look for a shortcut key without the Windows-Logo key press.
+  if (!aIgnore.mOS && (aEvent.modifiers & MODIFIER_OS)) {
+    IgnoreModifierState ignoreModifierState(aIgnore);
+    ignoreModifierState.mOS = true;
+    return FindMatchInternal(aEvent, ignoreModifierState, aOverrideCharCode);
+  }
+#endif
+
+  return Nothing();
+}
+
 } // namespace layers
 } // namespace mozilla

--- a/gfx/layers/apz/src/Keyboard.h
+++ b/gfx/layers/apz/src/Keyboard.h
@@ -5,23 +5,27 @@
 
 #ifndef mozilla_layers_Keyboard_h
 #define mozilla_layers_Keyboard_h
 
 #include <stdint.h> // for uint32_t
 
 #include "InputData.h"          // for KeyboardInput
 #include "nsIScrollableFrame.h" // for nsIScrollableFrame::ScrollUnit
+#include "nsTArray.h"           // for nsTArray
+#include "mozilla/Maybe.h"      // for mozilla::Maybe
 
 namespace mozilla {
 
 struct IgnoreModifierState;
 
 namespace layers {
 
+class KeyboardMap;
+
 /**
  * This class represents a scrolling action to be performed on a scrollable layer.
  */
 struct KeyboardScrollAction final
 {
 public:
   enum KeyboardScrollActionType : uint8_t
   {
@@ -70,16 +74,19 @@ public:
    * the keyboard event and dispatching it to content.
    */
   KeyboardShortcut(KeyboardInput::KeyboardEventType aEventType,
                    uint32_t aKeyCode,
                    uint32_t aCharCode,
                    Modifiers aModifiers,
                    Modifiers aModifiersMask);
 
+protected:
+  friend mozilla::layers::KeyboardMap;
+
   bool Matches(const KeyboardInput& aInput,
                const IgnoreModifierState& aIgnore,
                uint32_t aOverrideCharCode = 0) const;
 
 private:
   bool MatchesKey(const KeyboardInput& aInput,
                   uint32_t aOverrideCharCode) const;
   bool MatchesModifiers(const KeyboardInput& aInput,
@@ -102,12 +109,36 @@ public:
 
   // The type of keyboard event to match against
   KeyboardInput::KeyboardEventType mEventType;
 
   // Whether events matched by this must be dispatched to content
   bool mDispatchToContent;
 };
 
+/**
+ * A keyboard map is an off main-thread <xul:binding> for scrolling commands.
+ */
+class KeyboardMap final
+{
+public:
+  KeyboardMap();
+  explicit KeyboardMap(nsTArray<KeyboardShortcut>&& aShortcuts);
+
+  const nsTArray<KeyboardShortcut>& Shortcuts() const { return mShortcuts; }
+
+  /**
+   * Search through the internal list of shortcuts for a match for the input event
+   */
+  Maybe<KeyboardShortcut> FindMatch(const KeyboardInput& aEvent) const;
+
+private:
+  Maybe<KeyboardShortcut> FindMatchInternal(const KeyboardInput& aEvent,
+                                            const IgnoreModifierState& aIgnore,
+                                            uint32_t aOverrideCharCode = 0) const;
+
+  nsTArray<KeyboardShortcut> mShortcuts;
+};
+
 } // namespace layers
 } // namespace mozilla
 
 #endif // mozilla_layers_Keyboard_h

--- a/gfx/layers/ipc/LayersMessageUtils.h
+++ b/gfx/layers/ipc/LayersMessageUtils.h
@@ -16,16 +16,17 @@
 #include "mozilla/GfxMessageUtils.h"
 #include "mozilla/layers/AsyncDragMetrics.h"
 #include "mozilla/layers/CompositorOptions.h"
 #include "mozilla/layers/CompositorTypes.h"
 #include "mozilla/layers/GeckoContentController.h"
 #include "mozilla/layers/Keyboard.h"
 #include "mozilla/layers/LayerAttributes.h"
 #include "mozilla/layers/LayersTypes.h"
+#include "mozilla/Move.h"
 
 #include <stdint.h>
 
 #ifdef _MSC_VER
 #pragma warning( disable : 4800 )
 #endif
 
 namespace IPC {
@@ -466,16 +467,37 @@ struct ParamTraits<mozilla::layers::Keyb
            ReadParam(aMsg, aIter, &aResult->mCharCode) &&
            ReadParam(aMsg, aIter, &aResult->mModifiers) &&
            ReadParam(aMsg, aIter, &aResult->mModifiersMask) &&
            ReadParam(aMsg, aIter, &aResult->mEventType) &&
            ReadParam(aMsg, aIter, &aResult->mDispatchToContent);
   }
 };
 
+template <>
+struct ParamTraits<mozilla::layers::KeyboardMap>
+{
+  typedef mozilla::layers::KeyboardMap paramType;
+
+  static void Write(Message* aMsg, const paramType& aParam)
+  {
+    WriteParam(aMsg, aParam.Shortcuts());
+  }
+
+  static bool Read(const Message* aMsg, PickleIterator* aIter, paramType* aResult)
+  {
+    nsTArray<mozilla::layers::KeyboardShortcut> shortcuts;
+    if (!ReadParam(aMsg, aIter, &shortcuts)) {
+      return false;
+    }
+    *aResult = mozilla::layers::KeyboardMap(mozilla::Move(shortcuts));
+    return true;
+  }
+};
+
 typedef mozilla::layers::GeckoContentController::TapType TapType;
 
 template <>
 struct ParamTraits<TapType>
   : public ContiguousEnumSerializer<
              TapType,
              TapType::eSingleTap,
              TapType::eSentinel>