Posted on

Hacking NSMenu keyboard navigation

AppKit’s menu subsystem is perhaps one of the most rigid and monolithic components in Cocoa. While it has a quite clear API, it contradicts with many idioms assumed in Cocoa, especially regarding customization support.

NSMenu subsystem provides, basically, two major customization points:

  • You can set your NSMenuDelegate implementation to update a structure of a specific menu instance. All NSMenuDelegate’s hooks are called before the menu is displayed.
  • You can put a custom view inside some NSMenuItem element to present a non-regular or an area-specific type of information. Microsoft Office for Mac, for example, has loads of such custom menu elements.

Apart from these points, you can’t control the menu’s behavior. Apparently, there’re some good reasons for that rigidity. A lot of under-the-hood work is done without even bothering on the app side, for instance: a Help->Search functionality triggered via Cmd+Shift+? hotkey. Or, generally speaking, it’s an example of a principle of least user astonishment in action.

What if, however, you want to slightly alter a default routine of input processing? The universal answer is – “then go and write your own implementation from the scratch”. This WWDC session contains more details: “Key Event Handling in Cocoa Applications“. Of course, writing an additional UI component with several KSLoCs might be an entertaining adventure, but polishing every detail of such generic metaphor can easily eat up weeks of work. And, it turns out, usually, there are more important tasks to do.

In my specific case, I wanted to optimize a keyboard navigation of one particular UX pattern in Nimble Commander. It provides hotkeys to show popup menus with various places to navigate go, like favorite locations, mounted volumes, network connections etc. After such popup menu has been shown, a user can choose an appropriate location via arrows keys or via mouse. NC also sets up hotkeys for the first 12 elements: [0, 1, …, 0, -, =]. So, for short lists everything is fine, and a required location can be chosen with two keystrokes – first to pop up a menu and second to trigger a menu item. Longer lists, however, can become hard to navigate, since a required item can be accessed only with key arrows. Yes, there’s some basic letter-based navigation implemented in menus, but it’s absolutely rudimentary and won’t help much. What I wanted was plain and simple – to drop a few letters in the menu and to show only items which contain this substring in their titles. Something similar to this:

No googling gave me any hints on possible approaches to intercepting of NSMenu input. Cocoa’s menu subsystem doesn’t use a regular NSWindow/NSView event routing, so usual hooks can’t be applied in this situation. [NSEvent addLocalMonitorForEventsMatchingMask: handler:] doesn’t do a thing – there’s simply no NSEvent object to process. Perhaps [NSEvent addGlobalMonitorForEventsMatchingMask: handler:] could work, but it’s too heavy to use in a mere UI element.
What else? Anyone who debugged their code after it was called by a menu item, might have noticed that a call stack was full of identifiers containing a word “Carbon”. While a majority of Carbon API was marked as “deprecated” years ago, the menu subsystem still heavily relies on that code.
Well, that’s something at least. Luckily, an event-processing part of Carbon is still available and even wasn’t marked as “deprecated”.

So, with that tested and confirmed, it’s possible to switch to an actual “hack” implementation. Here’re the steps to intercept an incoming NSMenu event:
1. Make a custom menu.
2. Put there an element with a custom view inside.
3. Override the [NSView viewDidMoveToWindow] method on that custom view.
4. Retrieve current Carbon event dispatcher via GetEventDispatcherTarget().
5. Install a new event handler for an appropriate event kind via InstallEventHandler().

Here’s the code snippet (Objective-C++):

- (void) viewDidMoveToWindow
{
  [super viewDidMoveToWindow];

  if( m_EventHandler != nullptr ) {
    RemoveEventHandler(m_EventHandler);
    m_EventHandler = nullptr;
  }

  if( const auto window = self.window ) {
    if( ![window.className isEqualToString:@"NSCarbonMenuWindow"] ) {
      NSLog(@"Sorry, but MGKMenuWithFilter was designed to work with NSCarbonMenuWindow.");
      return;
    }
 
    const auto dispatcher = GetEventDispatcherTarget();
    if( !dispatcher ) {
      NSLog(@"GetEventDispatcherTarget() failed");
      return;
    }

    EventTypeSpec evts[2];
    evts[0].eventClass = kEventClassKeyboard;
    evts[0].eventKind = kEventRawKeyDown;
    evts[1].eventClass = kEventClassKeyboard;
    evts[1].eventKind = kEventRawKeyRepeat;
    const auto result = InstallEventHandler(dispatcher,
                                            CarbonCallback,
                                            2,
                                            &evts[0],
                                            (__bridge void*)self,
                                            &m_EventHandler);
    if( result != noErr ) {
      NSLog(@"InstallEventHandler() failed");
    }
  }
}

At this point, most of the keyboard events are passed to the custom Carbon callback, except for previously set key equivalents. The callback can convey these events onto the custom processing, and if an event wasn’t processed there, it can be sent back to default route:

static OSStatus CarbonCallback(EventHandlerCallRef _handler,
                               EventRef _event,
                               void *_user_data)
{
  if( !_event || !_user_data )
    return noErr;

  const auto menu_item = (__bridge MGKFilterMenuItem*)_user_data;
 
  const auto processed = [menu_item processInterceptedEvent:_event];
 
  if( processed )
    return noErr;
  else
    return CallNextEventHandler( _handler, _event );
}

It’s possible to convert EventRef into an NSEvent object with the following initializer: [NSEvent eventWithEventRef:]. Once NSEvent is received, any appropriate handling can be applied. In the current implementation, the top menu item contains an NSTextField view with a search criteria, which is shown only when some filter was entered. After a string inside this text field is updated, control is handed to the menu object so it can hide or show matching items, this process is quite straightforward. There are some details worth mentioning here:

  • It’s quite convenient to automatically select the first matching menu item after applying a filter if there was no selection before. NSMenu does not provide such interface, but it can be added with another dirty hack:
- (void) higlightCustomItem:(NSMenuItem*)_item
{
  static const auto selHighlightItem = NSSelectorFromString(@"highlightItem:");
  static const auto hack_works = (bool)[self respondsToSelector:selHighlightItem];
  if( hack_works ) {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Warc-performSelector-leaks"
    [self performSelector:selHighlightItem withObject:_item];
#pragma clang diagnostic pop
  }
}

 

  • After a filter was applied, any previously set key equivalents must be cleared and vice versa. Otherwise, they can be unintentionally triggered instead of altering criteria for filtering.
  • These hacks are quite dirty and basically, nothing guarantees that they won’t stop working at any moment in the future. If (or when) an underlying NSMenu’s infrastructure will change radically, MGKMenuWithFilter will gracefully fall back to a regular menu behavior. At this moment, however, this infrastructure seems to be pretty stable and hasn’t got major changes for years.
    Current hack compatibility at the moment:
    macOS 10.12 “Sierra” – works
    OS X 10.11 “El Capitan” – works
    OS X 10.10 “Yosemite” – works
    OS X 10.9 “Mavericks” – works
    OS X 10.8 “Mountain Lion” – works
    Mac OS X 10.7 “Lion” – works partially, there’s no [NSMenu highlightItem:]
  • Current implementation assumes a programmatic approach of populating a menu, but with minor changes, it can be extended to support NIB-based menus made in Interface Builder as well.

The source code is available in this repository.
It also includes example projects written in Swift, Objective-C and a project in Objective-C for pre-Yosemite versions of MacOSX.

Posted on

Updates on fixed_eytzinger_map

This is a brief report on some progress regarding fixed_eytzinger_map and code around it:

  • SFINAE expressions used in heterogeneous lookup were altered to be supported by Microsoft’s compiler (VS2015+).
  • The corresponding test suite was integrated with Catch testing framework.
    Now the source code comes with a makefile/CMakeLists.txt build script, which can compile and start tests, e.g. “make && make test“.
  • The source code is now being automatically tested by:
    • Travis CI:
      • Linux, x86-64
      • GCC 4.8/4.9/5.0 and clang 3.6/3.7/3.8
      • C++11/C++14
    • AppVeyor:
      • Windows, x86/x86-64
      • VisualStudio 2015/2017
      • C++11
  • A corresponding GitHub repository has got a decent readme page.
  • fixed_eytzinger_map is successfully used in Nimble Commander to manage various relationships between UI elements and corresponding action shortcuts.

Currently it seems that this project can be marked as “finished”, as there’s no obvious direction for evolution.

Posted on

Cache-friendly associative container

Few weeks ago I stumbled upon a nice blogpost describing a flat tree layout optimized for cache locality. Another profound work, in the form of scientific paper, entitled “Array layouts for comparison-based searching” also deserves mentioning. The basic idea there is that the commonly used layout of flat maps, i.e. an array of sorted key values, has the negative side-effect of a not-ideal cache locality. When doing a binary search, memory is accessed on distant positions and every such lookup might cause a cache miss.

The level-order layout (aka BFS or Eytzinger layout) utilizes a different approach. Instead of placing keys in a non-descending order, they are laid out in the order of binary search traversal. This leads to fewer cache misses and thus to better lookup times, especially on big trees. Of course, nothing comes for free, and there are two major drawbacks of this data structure:

  • Terrible complexity of per-element insertion/deletion, which makes such modifying operations barely usable. However, many containers are modified only on initialization stage and accessed in read-only mode afterwards. This especially plays well with the immutable data ideology.
  • Lack of “cheap” ordered traversal, like std::map/boost::flat_map has. A simple answer to this issue might be accepting the fact that traversing such structures is not ordered, exactly like in the case of std::unordered_map.

That said, I’ve decided to try to implement a generic STL-like associative map with Eytzinger layout, providing interface as close to drop-in replacement as it can be. Here’s the fixed_eytzinger_map source code.

 

Design considerations

  • This map is supposed to be a read-only structure, i.e. support only construction and per-element access. However, while keys order is defined upon construction, it’s still possible to alter the values these keys are mapping to.
  • Construction of a new map can be done with std::initializer_list or with a range of InputIterators.
  • operator= makes it possible to change the map’s content, filling it with another map or with a pair of iterators as the source.
  • operator[] has different semantics compared with std::map/std::unordered_map. It can’t add new entries, but [] is too handy for element access to discard it. In case of absent key the map will simply throw an exception, just as at() does.
  • This map uses two memory blocks to store keys and values separately. Instead of using std::pair<key, value>, which creates gaps between keys and thus decreasing SNR when performing lookups, this approach leads to a better memory locality.
  • Since the data is stored in separate locations, iterators can’t provide references to “real” std::pair<key, value> objects. Instead, they have to return proxy std::pair<key&, value&> objects.
  • C++14’s heterogeneous lookup can be enabled via std::less<> comparison operator or any other declaring is_transparent type. Heterogeneous lookup is available for all methods involving search: at, operator[], count, find, equal_range, lower_bound and upper_bound.
  • There’re no rbegin/rend methods, as iteration is not ordered by “less” operator and reverting the internal order wouldn’t make any sense.

 

Performance tests

Various measurements were done to compare fixed_eytzinger_map with the following containers: std::map (libc++3.7), std::unordered_map (libc++3.7), boost::flat_map (1.55).
Compilation was made by clang-800.0.42.1, x64 target, -Os.
Executed on i7-3615QM, running macOS 10.12.2.
X-axis represents amount of elements in the container, Y-axis shows μs/bytes per element.

Lookup times.
This measures how much time is spent on .count(..) method. The sequence of keys to search is semi-random with the fixed seed.

 

Lookup & fetch times.
Similar to the previous graph, but uses the .at(..) method to actually access the values pointed by keys.

 

Construction times.
This measures the time spent on the construction of an associative container from a semi-random std::vector<std::pair<Key,Value>>, performing a single lookup and cleaning up afterwards.

 

Memory consumption.
How much memory is used to construct a container. It’s a bit hard to measure directly, so instead what is shown here is a delta between the memory consumed by test process before and after building a container.

 

Results

It’s not easy to compare these data structures directly, as each has it’s unique properties. However, what can be said, is that Eytzinger layout is always outperforms a sorted array (boost::flat_map) and consumes 2x to 5x less memory than std::unordered_map does. If immutability is not an issue, fixed_eytzinger_map might be worth trying at least.