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.

Extracting extended attributes from Apple Double format

When files from native MacOSX filesystems (like HFS+) are copied to some storage that doesn’t support extended attributes (xattrs) natively, those attributes are not lost, instead they are placed in special files with a “._” prefix. For archives these paths may also contain “__MACOSX/” directory prefix.
These files have an ancient format called AppleDouble, which once was well documented but sadly lacks any support from current-gen Apple’s APIs.
Sometimes it’s necessary to work with such format, in my case – with compressed files inside zip archives. Ignoring separately-stored extended attributes may cause unwished consequences, mostly related with a user experience (invalid encodings, lost Finder’s labels etc) and is generally bad.
Here below is a code snippet which parses “._” file’s content and extracts a list of extended attributes with it’s data. This data may be passed to setxattr(..) function or be interpreted somehow. Some structures layout and functions are taken from Apple’s copyfile.c source.

Header (AppleDouble.h):
#pragma once
#include <stdint.h>
struct AppleDoubleEA
{
    // no allocations, only pointing at original memory buffer
    const void* data;
    const char* name; // null-terminated UTF-8 string
    uint32_t    data_sz;
   uint32_t    name_len; // length excluding zero-terminator. no zero-length names are allowed
};

/**
 * ExtractEAFromAppleDouble interprets a memory block of EAs packed into AppleDouble file, usually for archives.
 * Returns NULL or an array of AppleDoubleEA (number of _ea_count) allocated with malloc.
 * Caller is responsible for deallocating this memory.
 */
AppleDoubleEA *ExtractEAFromAppleDouble(const void *_memory_buf,
                                        size_t      _memory_size,
                                        size_t     *_ea_count
                                        );

Source file (AppleDouble.cpp):
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/xattr.h>
#include <libkern/OSByteOrder.h>
#include “AppleDouble.h”

#define ADH_MAGIC     0x00051607
#define ADH_VERSION   0x00020000
#define ADH_MACOSX    “Mac OS X        “
#define AD_DATA          1   /* Data fork */
#define AD_RESOURCE      2   /* Resource fork */
#define AD_REALNAME      3   /* File’s name on home file system */
#define AD_COMMENT       4   /* Standard Mac comment */
#define AD_ICONBW        5   /* Mac black & white icon */
#define AD_ICONCOLOR     6   /* Mac color icon */
#define AD_UNUSED        7   /* Not used */
#define AD_FILEDATES     8   /* File dates; create, modify, etc */
#define AD_FINDERINFO    9   /* Mac Finder info & extended info */
#define AD_MACINFO      10   /* Mac file info, attributes, etc */
#define AD_PRODOSINFO   11   /* Pro-DOS file info, attrib., etc */
#define AD_MSDOSINFO    12   /* MS-DOS file info, attributes, etc */
#define AD_AFPNAME      13   /* Short name on AFP server */
#define AD_AFPINFO      14   /* AFP file info, attrib., etc */
#define AD_AFPDIRID     15   /* AFP directory ID */
#define AD_ATTRIBUTES   AD_FINDERINFO
#define ATTR_HDR_MAGIC     0x41545452   /* ‘ATTR’ */
#define FINDERINFOSIZE 32

#pragma pack(1)
typedef struct apple_double_entry
{
u_int32_t   type;     /* entry type: see list, 0 invalid */
u_int32_t   offset;   /* entry data offset from the beginning of the file. */
u_int32_t   length;   /* entry data length in bytes. */
} apple_double_entry_t;

/* Entries are aligned on 4 byte boundaries */
typedef struct attr_entry
{
u_int32_t   offset;    /* file offset to data */
u_int32_t   length;    /* size of attribute data */
u_int16_t   flags;
u_int8_t    namelen;   /* length of name including NULL termination char */
u_int8_t    name[1];   /* NULL-terminated UTF-8 name (up to 128 bytes max) */
} attr_entry_t;

typedef struct apple_double_header
{
u_int32_t   magic;         /* == ADH_MAGIC */
u_int32_t   version;       /* format version: 2 = 0x00020000 */
u_int32_t   filler[4];
u_int16_t   numEntries;   /* number of entries which follow */
apple_double_entry_t   entries[2];  /* ‘finfo’ & ‘rsrc’ always exist */
u_int8_t    finfo[FINDERINFOSIZE];  /* Must start with Finder Info (32 bytes) */
u_int8_t    pad[2];        /* get better alignment inside attr_header */
} apple_double_header_t;

/* Header + entries must fit into 64K <– guess not true since 10.7 .MK. */
typedef struct attr_header
{
apple_double_header_t  appledouble;
u_int32_t   magic;        /* == ATTR_HDR_MAGIC */
u_int32_t   debug_tag;    /* for debugging == file id of owning file */
u_int32_t   total_size;   /* total size of attribute header + entries + data */
u_int32_t   data_start;   /* file offset to attribute data area */
u_int32_t   data_length;  /* length of attribute data area */
u_int32_t   reserved[3];
u_int16_t   flags;
u_int16_t   num_attrs;
} attr_header_t;
#pragma pack()

#define SWAP16(x) OSSwapBigToHostInt16(x)
#define SWAP32(x) OSSwapBigToHostInt32(x)
#define SWAP64(x) OSSwapBigToHostInt64(x)
#define ATTR_ALIGN 3L  /* Use four-byte alignment */
#define ATTR_DATA_ALIGN 1L  /* Use two-byte alignment */
#define ATTR_ENTRY_LENGTH(namelen)  
((sizeof(attr_entry_t) – 1 + (namelen) + ATTR_ALIGN) & (~ATTR_ALIGN))
#define ATTR_NEXT(ae)  
(attr_entry_t *)((u_int8_t *)(ae) + ATTR_ENTRY_LENGTH((ae)->namelen))

static const u_int32_t emptyfinfo[8] = {0};

/*
 * Endian swap Apple Double header
 */
static void
swap_adhdr(apple_double_header_t *adh)
{
   int count;
   int i;
    
   count = (adh->magic == ADH_MAGIC) ? adh->numEntries : SWAP16(adh->numEntries);
    
   adh->magic      = SWAP32 (adh->magic);
   adh->version    = SWAP32 (adh->version);
   adh->numEntries = SWAP16 (adh->numEntries);
    
   for (i = 0; i < count; i++)
   {
      adh->entries[i].type   = SWAP32 (adh->entries[i].type);
      adh->entries[i].offset = SWAP32 (adh->entries[i].offset);
      adh->entries[i].length = SWAP32 (adh->entries[i].length);
   }
}

/*
 * Endian swap extended attributes header
 */
static void
swap_attrhdr(attr_header_t *ah)
{
   ah->magic       = SWAP32 (ah->magic);
   ah->debug_tag   = SWAP32 (ah->debug_tag);
   ah->total_size  = SWAP32 (ah->total_size);
   ah->data_start  = SWAP32 (ah->data_start);
   ah->data_length = SWAP32 (ah->data_length);
   ah->flags       = SWAP16 (ah->flags);
   ah->num_attrs   = SWAP16 (ah->num_attrs);
}

static bool IsAppleDouble(const void *_memory_buf, size_t _memory_size)
{
    const apple_double_header_t *adhdr = (const apple_double_header_t *)_memory_buf;
    if(_memory_size < sizeof(apple_double_header_t) – 2 ||
       SWAP32(adhdr->magic) != ADH_MAGIC ||
       SWAP32(adhdr->version) != ADH_VERSION ||
       SWAP16(adhdr->numEntries) != 2 ||
       SWAP32(adhdr->entries[0].type) != AD_FINDERINFO
       )
        return false;
    
    return true;
}

AppleDoubleEA *ExtractEAFromAppleDouble(const void *_memory_buf,
                                        size_t      _memory_size,
                                        size_t     *_ea_count
                                        )
{
    if(!_memory_buf || !_memory_size || !_ea_count)
        return 0;
    
    if(!IsAppleDouble(_memory_buf, _memory_size))
        return 0;
    
    apple_double_header_t adhdr = *(const apple_double_header_t *) _memory_buf;
    swap_adhdr(&adhdr);
    
    bool has_finfo = memcmp(adhdr.finfo, emptyfinfo, sizeof(emptyfinfo)) != 0;
    
    AppleDoubleEA *eas = 0;
    int eas_last = 0;
    
    if(adhdr.entries[0].length > FINDERINFOSIZE)
    {
        attr_header_t attrhdr = *(const attr_header_t *)_memory_buf;
        swap_attrhdr(&attrhdr);
        
        if (attrhdr.magic == ATTR_HDR_MAGIC)
        {
            int count = attrhdr.num_attrs;
            eas = (AppleDoubleEA*) malloc( sizeof(AppleDoubleEA) * (has_finfo ? count + 1 : count) );
            
            const attr_entry_t *entry = (const attr_entry_t *)((char*)_memory_buf + sizeof(attr_header_t));
            for (int i = 0; i < count; i++)
            {
                if((char*)entry + sizeof(attr_entry_t) > (char*)_memory_buf + _memory_size)
                    break; // out-of-boundary guard to be safe about memory (not)corrupting
                
                u_int32_t offset = SWAP32(entry->offset);
                u_int32_t length = SWAP32(entry->length);
                u_int32_t namelen = 0;
                const char *name = (const char*)&entry->name[0];
                
                // safely calculate a name len
                for(const char *si = name; si < (char*)_memory_buf + _memory_size && (*si) != 0; ++si, ++namelen)
                    ;
                
                
                if(namelen > 0 &&
                   name + namelen < (char*)_memory_buf + _memory_size &&
                   name[namelen] == 0 &&
                   offset + length <= _memory_size)
                { // seems to be a valid EA
                    eas[eas_last].data = (char*)_memory_buf + offset;
                    eas[eas_last].data_sz = length;
                    eas[eas_last].name = name;
                    eas[eas_last].name_len = namelen;
                    ++eas_last;
                }
                entry = ATTR_NEXT(entry);
            }
        }
    }
    
    if(has_finfo)
    {
        if(!eas) // no extended attributes except FinderInfo was found
            eas = (AppleDoubleEA*) malloc( sizeof(AppleDoubleEA) );
        eas[eas_last].data = &((const apple_double_header_t *)_memory_buf)->finfo[0];
        eas[eas_last].data_sz = 32;
        eas[eas_last].name = XATTR_FINDERINFO_NAME; // “com.apple.FinderInfo”
        eas[eas_last].name_len = 20;
        ++eas_last;
    }
    
    *_ea_count = eas_last;
    
    return eas;
}

8 bytes that’ll drive you mad

Today I’ve discovered a very strange bug in my software: after using an internal viewer in Files with PkgInfo in app package, Files crashes randomly and alerting on memory corruption.
Something like this:
Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
or this:
Files(85331,0x7fff7e8cc310) malloc: *** error for object 0x600000018a70: Heap corruption detected, free list canary is damaged
*** set a breakpoint in malloc_error_break to debug

A following story is below.


It was funny, since this viewer can easily handle a gigabyte-scale files. So I blamed the last refactoring and checked previous releases. They crash too, with the same symptoms.
Ok, I started investigations.
PkgInfo is 8-bytes file with text APPL????.
Copied this file to another place (some system-level locks maybe?) and viewed it. Crash.
Renamed file. Crash.
Created another 8-byte file with content 01234567 and tried it. Crash.
Created 7-byte and 9-byte files and tried them. Worked like a charm. Hmm…
It was something definitely related with alignment logic somewhere in low-level modules.
My suspicions fall onto data analysis module, which answers the questions like “what is the likely encoding for this bulk of data?” or “is this bulk of data binary or text?”.
Turned off this module and tried 8-byte file again. Crash.
Things becoming worse since sometimes viewer crashed even before it’s logic (layout, render, navigation etc) get to work.
Desperately I start tracking everything down from the very beginning of viewer’s initialization and came to my string decoders. At least it was a place where memory can become corrupted and I’ve changed encoding to Western (Mac OS Roman) from UTF-8 to see any difference. Worked like a charm. Hmm…
A few minutes later I finally stopped on relatively old UTF-8 conversion function:
void InterpretUTF8BufferAsIndexedUniChar(
const unsigned char* _input,
size_t _input_size,
unsigned short *_output_buf, // should be at least _input_size 16b words long
uint32_t *_indexes_buf, // should be at least _input_size 32b words long
size_t *_output_sz, // size of an output
unsigned short _bad_symb // something like ‘?’ or U+FFFD
)

And after tracing the decoding of 8 bytes “01234567” I finally stopped at a humble line:
    *_output_buf = 0;
}
That’s a zero-terminating of resulting UniChar buffer. But! -> // should be at least _input_size 16b words long
When looked into upper-level calling code there was a precise memory allocation for this buffer:
m_DecodeBuffer = (UniChar*) calloc(m_FileWindow->WindowSize(), sizeof(UniChar));
So when file is 8-bytes long – the allocated memory is precisely 8 bytes long (when is was 7 or 9 bytes then allocation size was aligned onto some boundary and writing a zero-terminator didn’t cause any effect) and zeroing it (m_DecodeBuffer[8]=0) resulting in corruption of a following heap controlling structures, which causes a crash later.
Of course this zero-termination was unnecessary since every later function operating with UniChar buffer don’t rely on it’s zero-terminator.
The quest was complete.

A “million files” test

Writing a file manager is definitely a quite special kind of fun. Despite a seeming simplicity there’s a lot of details that should be considered when implementing it. Using efficient structures, algorithms and architecture can mean much, regardless that all remains under the hood and is not visible to user. Since the main purpose of a file management app is navigation between folders and showing their’s content, I’ve managed to perform some tests to show how different implementations can handle this (quite simple?) task. At the moment my collection of Mac OS X file managers was 11 different ones (all this software can be easily found in Google, also I don’t claim I’ve tested all file managers for Mac OS X – there’re others).
OK, to be precise – this is a stress test. By stress I mean not a usual stress, but STRESS.
The job is very simple: reading and showing a content of a directory with 1,000,000 files. Nothing more, just it. I’ve taken my old 8Gb USB stick, plugged it into my Macbook Pro running OS X Mavericks and formatted it into HFS+ journaled, also turned off Spotlight on this volume. Then run a tiny app, which I called fs_killer 🙂
int main(int argc, const char * argv[]) {
    char tmp[MAXPATHLEN];
    for(int i = 0; i < 1000000; ++i) {
        sprintf(tmp, “/Volumes/test/%6.6d.txt”, i);
        close(open(tmp, O_WRONLY|O_CREAT, S_IRUSR|S_IWUSR|S_IRGRP));
    }
    return 0;
}

Here’s the test itself: run an app, check if it will be able to open this folder, record how much memory it has consumed and check if app is still usable (cursor movements and scrolling ability). Every app was given a plenty of time to load the directory listing, and this parameter wasn’t counted. The comparison table in alphabetical order is below:

Results
Application name Opened Memory Usable
DCommander yes ~1.7Gb yes
FastCommander yes ~1.1Gb yes
Nimble Commander yes 150Mb yes
Finder
yes
~2Gb yes
ForkLift yes ~1.7Gb yes
Macintosh Explorer yes ~1Gb yes
Midnight Commander yes 133Mb yes
Moroshka File Manager yes 160Mb no
Mover yes ~2Gb no
muCommander no n/a n/a
ZCommander yes 850Mb yes
A few words for conclusion. Two things can be clearly seen:
1) Midnight Commander (mc) is the winner (and the only to run in console) and muCommander is very bad – it was the only one to fail the opening test.
2) These file managers can be divided into 2 groups by memory consumption: less than roughly 200Mb and above it. I suppose this difference to be consequence of an internal data storage structure – while the first group relies on plain C / C++ memory management, the others use Objective C / Cocoa infrastructure to handle directory listing data, which is considerable less efficient in this aspect.
As the bottom line I can only give a link to Nimble Commander, it’s free now: http://magnumbytes.com/