[Remoting Host] Handle text event characters that are not presented on the keyboard

remoting/host/linux/x_server_key_mapper.cc

Index: remoting/host/linux/x_server_key_mapper.cc
diff --git a/remoting/host/linux/x_server_key_mapper.cc b/remoting/host/linux/x_server_key_mapper.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8eca217013184757539271489323c703f3c3bf0e
--- /dev/null
+++ b/remoting/host/linux/x_server_key_mapper.cc
@@ -0,0 +1,65 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "remoting/host/linux/x_server_key_mapper.h"
+
+#include "base/time/time.h"
+#include "remoting/host/linux/keyboard_interface.h"
+
+namespace {
+
+// The minimum duration before a mapped keycode can be reused.
+constexpr base::TimeDelta kMinReuseDuration =
+    base::TimeDelta::FromMilliseconds(200);
+
+}  // namespace
+
+namespace remoting {
+
+struct XServerKeyMapper::KeyInfo {
+  uint32_t keycode;
+  base::TimeTicks last_used_time;
+};
+
+XServerKeyMapper::XServerKeyMapper(KeyboardInterface* keyboard)
+    : keyboard_(keyboard) {
+  std::vector<uint32_t> keycodes = keyboard_->GetUnusedKeycodes();
+  for (uint32_t keycode : keycodes) {
+    available_keycodes_.push_back({keycode, base::TimeTicks()});
+  }
+}
+
+XServerKeyMapper::~XServerKeyMapper() {
+  // Clear all used key mappings.
+  for (const KeyInfo& info : available_keycodes_) {
+    if (!info.last_used_time.is_null()) {
+      keyboard_->ChangeKeyMapping(info.keycode, 0, 0);
+    }
+  }
+  keyboard_->Sync();
+}
+
+XServerKeyMapper::MapResult XServerKeyMapper::AddNewCharacter(
+    uint32_t code_point) {
+  KeyInfo& info = available_keycodes_[current_keycode_index_];
+
+  base::TimeDelta time_until_reusable =
+      info.last_used_time + kMinReuseDuration - base::TimeTicks::Now();
+  if (time_until_reusable > base::TimeDelta()) {
+    return {false, 0, time_until_reusable};
+  }
+
+  if (!keyboard_->ChangeKeyMapping(info.keycode, code_point, code_point)) {
+    return {false, 0, base::TimeDelta()};
+  }
+
+  info.last_used_time = base::TimeTicks::Now();

[Sergey Ulanov, 2016/09/21 19:59:23]

I think we also want to update last_used_time later, when the key gets reused.
AddNewCharacter() currently is not invoked in that case.
It's best to to put all keys in a heap to make this efficient.

[Yuwei, 2016/09/21 20:35:32]

Since the time here is just to prevent remapping before last_used_time +
kMinReuseDuration, I don't think changing it when no remapping takes place is
necessary. Maybe just rename it to last_mapped_time?
SGTM. I'll add a field "use_count" in the struct.

[Sergey Ulanov, 2016/09/21 20:55:23]

I think we want to track the time when the mapping is used, not just when it's
first mapped. If you inject a key event and immediately change mapping for that
key then the receiving application may process the event with the updated
mapping, i.e. it will get incorrect character. Apps get just keycode as part of
XKeyEvent and they need to map each event to KeySym.

e.g. suppose we have 3 keys for remapping and we receive ABC and then AD after
300ms delay. In this case this code will inject the first key mapped to A and
then immediately remap it to D. As result the receiving application is likely to
get ABCDD instead of ABCAD
How would that be used? In the heap I think we want to order the keys by the
time they were used last time.

[Yuwei, 2016/09/21 21:14:18]

Got it. 
Sorry. I was thinking about reusing the least used keycode. That doesn't quite
work though since that ignores the minimum duration.

[Yuwei, 2016/09/22 00:32:58]

Looks like STL doesn't provide useful heap utility for updating the priority.
The only function that fixes the heap is std::make_heap, which is O(n). Moving
down the updated node can be O(log(n)) but whether the heap is binary is
implementation specific... Also you will need an extra map to locate the KeyInfo
from the keycode.

I'm just thinking whether we can use a tree set to minimize code complexity.
Even having an optimized heap implementation can't get any faster than O(log(n))
for adding (finding) character...

[Sergey Ulanov, 2016/09/22 18:32:46]

I think just putting everything in a sorted vector will work perfectly fine. We
will never have more than 255 elements here, so technically it's always O(1).
With that few elements the vector will fit in L1 cache anyway.

[Yuwei, 2016/09/23 01:40:37]

Done.

+  current_keycode_index_ =
+      (current_keycode_index_ + 1) % available_keycodes_.size();
+
+  keyboard_->Sync();
+  return {true, info.keycode, base::TimeDelta()};
+}
+
+}  // namespace remoting