<commit_before>/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import { CharCode } from 'vs/base/common/charCode';
import { KeyCode, KeyCodeUtils, Keybinding, ResolvedKeybinding, SimpleKeybinding } from 'vs/base/common/keyCodes';
import { OperatingSystem } from 'vs/base/common/platform';
import { IMMUTABLE_CODE_TO_KEY_CODE, IMMUTABLE_KEY_CODE_TO_CODE, ScanCode, ScanCodeBinding, ScanCodeUtils } from 'vs/base/common/scanCode';
import { IKeyboardEvent } from 'vs/platform/keybinding/common/keybinding';
import { IKeyboardMapper } from 'vs/workbench/services/keybinding/common/keyboardMapper';
import { BaseResolvedKeybinding } from 'vs/platform/keybinding/common/baseResolvedKeybinding';

export interface IMacLinuxKeyMapping {
	value: string;
	withShift: string;
	withAltGr: string;
	withShiftAltGr: string;
}

function macLinuxKeyMappingEquals(a: IMacLinuxKeyMapping, b: IMacLinuxKeyMapping): boolean {
	if (!a && !b) {
		return true;
	}
	if (!a || !b) {
		return false;
	}
	return (
		a.value === b.value
		&& a.withShift === b.withShift
		&& a.withAltGr === b.withAltGr
		&& a.withShiftAltGr === b.withShiftAltGr
	);
}

export interface IMacLinuxKeyboardMapping {
	[scanCode: string]: IMacLinuxKeyMapping;
}

export function macLinuxKeyboardMappingEquals(a: IMacLinuxKeyboardMapping | null, b: IMacLinuxKeyboardMapping | null): boolean {
	if (!a && !b) {
		return true;
	}
	if (!a || !b) {
		return false;
	}
	for (let scanCode = 0; scanCode < ScanCode.MAX_VALUE; scanCode++) {
		const strScanCode = ScanCodeUtils.toString(scanCode);
		const aEntry = a[strScanCode];
		const bEntry = b[strScanCode];
		if (!macLinuxKeyMappingEquals(aEntry, bEntry)) {
			return false;
		}
	}
	return true;
}

/**
 * A map from character to key codes.
 * e.g. Contains entries such as:
 *  - '/' => { keyCode: KeyCode.US_SLASH, shiftKey: false }
 *  - '?' => { keyCode: KeyCode.US_SLASH, shiftKey: true }
 */
const CHAR_CODE_TO_KEY_CODE: ({ keyCode: KeyCode; shiftKey: boolean } | null)[] = [];

export class NativeResolvedKeybinding extends BaseResolvedKeybinding<ScanCodeBinding> {

	private readonly _mapper: MacLinuxKeyboardMapper;

	constructor(mapper: MacLinuxKeyboardMapper, os: OperatingSystem, parts: ScanCodeBinding[]) {
		super(os, parts);
		this._mapper = mapper;
	}

	protected _getLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getUILabelForScanCodeBinding(keybinding);
	}

	protected _getAriaLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getAriaLabelForScanCodeBinding(keybinding);
	}

	protected _getElectronAccelerator(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getElectronAcceleratorLabelForScanCodeBinding(keybinding);
	}

	protected _getUserSettingsLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getUserSettingsLabelForScanCodeBinding(keybinding);
	}

	protected _isWYSIWYG(binding: ScanCodeBinding | null): boolean {
		if (!binding) {
			return true;
		}
		if (IMMUTABLE_CODE_TO_KEY_CODE[binding.scanCode] !== -1) {
			return true;
		}
		let a = this._mapper.getAriaLabelForScanCodeBinding(binding);
		let b = this._mapper.getUserSettingsLabelForScanCodeBinding(binding);

		if (!a && !b) {
			return true;
		}
		if (!a || !b) {
			return false;
		}
		return (a.toLowerCase() === b.toLowerCase());
	}

	protected _getDispatchPart(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getDispatchStrForScanCodeBinding(keybinding);
	}
}

interface IScanCodeMapping {
	scanCode: ScanCode;
	value: number;
	withShift: number;
	withAltGr: number;
	withShiftAltGr: number;
}

class ScanCodeCombo {
	public readonly ctrlKey: boolean;
	public readonly shiftKey: boolean;
	public readonly altKey: boolean;
	public readonly scanCode: ScanCode;

	constructor(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, scanCode: ScanCode) {
		this.ctrlKey = ctrlKey;
		this.shiftKey = shiftKey;
		this.altKey = altKey;
		this.scanCode = scanCode;
	}

	public toString(): string {
		return `${this.ctrlKey ? 'Ctrl+' : ''}${this.shiftKey ? 'Shift+' : ''}${this.altKey ? 'Alt+' : ''}${ScanCodeUtils.toString(this.scanCode)}`;
	}

	public equals(other: ScanCodeCombo): boolean {
		return (
			this.ctrlKey === other.ctrlKey
			&& this.shiftKey === other.shiftKey
			&& this.altKey === other.altKey
			&& this.scanCode === other.scanCode
		);
	}

	private getProducedCharCode(mapping: IMacLinuxKeyMapping): string {
		if (!mapping) {
			return '';
		}
		if (this.ctrlKey && this.shiftKey && this.altKey) {
			return mapping.withShiftAltGr;
		}
		if (this.ctrlKey && this.altKey) {
			return mapping.withAltGr;
		}
		if (this.shiftKey) {
			return mapping.withShift;
		}
		return mapping.value;
	}

	public getProducedChar(mapping: IMacLinuxKeyMapping): string {
		const charCode = MacLinuxKeyboardMapper.getCharCode(this.getProducedCharCode(mapping));
		if (charCode === 0) {
			return ' --- ';
		}
		if (charCode >= CharCode.U_Combining_Grave_Accent && charCode <= CharCode.U_Combining_Latin_Small_Letter_X) {
			// combining
			return 'U+' + charCode.toString(16);
		}
		return '  ' + String.fromCharCode(charCode) + '  ';
	}
}

class KeyCodeCombo {
	public readonly ctrlKey: boolean;
	public readonly shiftKey: boolean;
	public readonly altKey: boolean;
	public readonly keyCode: KeyCode;

	constructor(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, keyCode: KeyCode) {
		this.ctrlKey = ctrlKey;
		this.shiftKey = shiftKey;
		this.altKey = altKey;
		this.keyCode = keyCode;
	}

	public toString(): string {
		return `${this.ctrlKey ? 'Ctrl+' : ''}${this.shiftKey ? 'Shift+' : ''}${this.altKey ? 'Alt+' : ''}${KeyCodeUtils.toString(this.keyCode)}`;
	}
}

class ScanCodeKeyCodeMapper {

	/**
	 * ScanCode combination => KeyCode combination.
	 * Only covers relevant modifiers ctrl, shift, alt (since meta does not influence the mappings).
	 */
	private readonly _scanCodeToKeyCode: number[][] = [];
	/**
	 * inverse of `_scanCodeToKeyCode`.
	 * KeyCode combination => ScanCode combination.
	 * Only covers relevant modifiers ctrl, shift, alt (since meta does not influence the mappings).
	 */
	private readonly _keyCodeToScanCode: number[][] = [];

	constructor() {
		this._scanCodeToKeyCode = [];
		this._keyCodeToScanCode = [];
	}

	public registrationComplete(): void {
		// IntlHash and IntlBackslash are rare keys, so ensure they don't end up being the preferred...
		this._moveToEnd(ScanCode.IntlHash);
		this._moveToEnd(ScanCode.IntlBackslash);
	}

	private _moveToEnd(scanCode: ScanCode): void {
		for (let mod = 0; mod < 8; mod++) {
			const encodedKeyCodeCombos = this._scanCodeToKeyCode[(scanCode << 3) + mod];
			if (!encodedKeyCodeCombos) {
				continue;
			}
			for (let i = 0, len = encodedKeyCodeCombos.length; i < len; i++) {
				const encodedScanCodeCombos = this._keyCodeToScanCode[encodedKeyCodeCombos[i]];
				if (encodedScanCodeCombos.length === 1) {
					continue;
				}
				for (let j = 0, len = encodedScanCodeCombos.length; j < len; j++) {
					const entry = encodedScanCodeCombos[j];
					const entryScanCode = (entry >>> 3);
					if (entryScanCode === scanCode) {
						// Move this entry to the end
						for (let k = j + 1; k < len; k++) {
							encodedScanCodeCombos[k - 1] = encodedScanCodeCombos[k];
						}
						encodedScanCodeCombos[len - 1] = entry;
					}
				}
			}
		}
	}

	public registerIfUnknown(scanCodeCombo: ScanCodeCombo, keyCodeCombo: KeyCodeCombo): void {
		if (keyCodeCombo.keyCode === KeyCode.Unknown) {
			return;
		}
		const scanCodeComboEncoded = this._encodeScanCodeCombo(scanCodeCombo);
		const keyCodeComboEncoded = this._encodeKeyCodeCombo(keyCodeCombo);

		const keyCodeIsDigit = (keyCodeCombo.keyCode >= KeyCode.KEY_0 && keyCodeCombo.keyCode <= KeyCode.KEY_9);
		const keyCodeIsLetter = (keyCodeCombo.keyCode >= KeyCode.KEY_A && keyCodeCombo.keyCode <= KeyCode.KEY_Z);

		const existingKeyCodeCombos = this._scanCodeToKeyCode[scanCodeComboEncoded];

		// Allow a scan code to map to multiple key codes if it is a digit or a letter key code
		if (keyCodeIsDigit || keyCodeIsLetter) {
			// Only check that we don't insert the same entry twice
			if (existingKeyCodeCombos) {
				for (let i = 0, len = existingKeyCodeCombos.length; i < len; i++) {
					if (existingKeyCodeCombos[i] === keyCodeComboEncoded) {
						// avoid duplicates
						return;
					}
				}
			}
		} else {
			// Don't allow multiples
			if (existingKeyCodeCombos && existingKeyCodeCombos.length !== 0) {
				return;
			}
		}

		this._scanCodeToKeyCode[scanCodeComboEncoded] = this._scanCodeToKeyCode[scanCodeComboEncoded] || [];
		this._scanCodeToKeyCode[scanCodeComboEncoded].unshift(keyCodeComboEncoded);

		this._keyCodeToScanCode[keyCodeComboEncoded] = this._keyCodeToScanCode[keyCodeComboEncoded] || [];
		this._keyCodeToScanCode[keyCodeComboEncoded].unshift(scanCodeComboEncoded);
	}

	public lookupKeyCodeCombo(keyCodeCombo: KeyCodeCombo): ScanCodeCombo[] {
		const keyCodeComboEncoded = this._encodeKeyCodeCombo(keyCodeCombo);
		const scanCodeCombosEncoded = this._keyCodeToScanCode[keyCodeComboEncoded];
		if (!scanCodeCombosEncoded || scanCodeCombosEncoded.length === 0) {
			return [];
		}

		let result: ScanCodeCombo[] = [];
		for (let i = 0, len = scanCodeCombosEncoded.length; i < len; i++) {
			const scanCodeComboEncoded = scanCodeCombosEncoded[i];

			const ctrlKey = (scanCodeComboEncoded & 0b001) ? true : false;
			const shiftKey = (scanCodeComboEncoded & 0b010) ? true : false;
			const altKey = (scanCodeComboEncoded & 0b100) ? true : false;
			const scanCode: ScanCode = (scanCodeComboEncoded >>> 3);

			result[i] = new ScanCodeCombo(ctrlKey, shiftKey, altKey, scanCode);
		}
		return result;
	}

	public lookupScanCodeCombo(scanCodeCombo: ScanCodeCombo): KeyCodeCombo[] {
		const scanCodeComboEncoded = this._encodeScanCodeCombo(scanCodeCombo);
		const keyCodeCombosEncoded = this._scanCodeToKeyCode[scanCodeComboEncoded];
		if (!keyCodeCombosEncoded || keyCodeCombosEncoded.length === 0) {
			return [];
		}

		let result: KeyCodeCombo[] = [];
		for (let i = 0, len = keyCodeCombosEncoded.length; i < len; i++) {
			const keyCodeComboEncoded = keyCodeCombosEncoded[i];

			const ctrlKey = (keyCodeComboEncoded & 0b001) ? true : false;
			const shiftKey = (keyCodeComboEncoded & 0b010) ? true : false;
			const altKey = (keyCodeComboEncoded & 0b100) ? true : false;
			const keyCode: KeyCode = (keyCodeComboEncoded >>> 3);

			result[i] = new KeyCodeCombo(ctrlKey, shiftKey, altKey, keyCode);
		}
		return result;
	}

	public guessStableKeyCode(scanCode: ScanCode): KeyCode {
		if (scanCode >= ScanCode.Digit1 && scanCode <= ScanCode.Digit0) {
			// digits are ok
			switch (scanCode) {
				case ScanCode.Digit1: return KeyCode.KEY_1;
				case ScanCode.Digit2: return KeyCode.KEY_2;
				case ScanCode.Digit3: return KeyCode.KEY_3;
				case ScanCode.Digit4: return KeyCode.KEY_4;
				case ScanCode.Digit5: return KeyCode.KEY_5;
				case ScanCode.Digit6: return KeyCode.KEY_6;
				case ScanCode.Digit7: return KeyCode.KEY_7;
				case ScanCode.Digit8: return KeyCode.KEY_8;
				case ScanCode.Digit9: return KeyCode.KEY_9;
				case ScanCode.Digit0: return KeyCode.KEY_0;
			}
		}

		// Lookup the scanCode with and without shift and see if the keyCode is stable
		const keyCodeCombos1 = this.lookupScanCodeCombo(new ScanCodeCombo(false, false, false, scanCode));
		const keyCodeCombos2 = this.lookupScanCodeCombo(new ScanCodeCombo(false, true, false, scanCode));
		if (keyCodeCombos1.length === 1 && keyCodeCombos2.length === 1) {
			const shiftKey1 = keyCodeCombos1[0].shiftKey;
			const keyCode1 = keyCodeCombos1[0].keyCode;
			const shiftKey2 = keyCodeCombos2[0].shiftKey;
			const keyCode2 = keyCodeCombos2[0].keyCode;
			if (keyCode1 === keyCode2 && shiftKey1 !== shiftKey2) {
				// This looks like a stable mapping
				return keyCode1;
			}
		}

		return -1;
	}

	private _encodeScanCodeCombo(scanCodeCombo: ScanCodeCombo): number {
		return this._encode(scanCodeCombo.ctrlKey, scanCodeCombo.shiftKey, scanCodeCombo.altKey, scanCodeCombo.scanCode);
	}

	private _encodeKeyCodeCombo(keyCodeCombo: KeyCodeCombo): number {
		return this._encode(keyCodeCombo.ctrlKey, keyCodeCombo.shiftKey, keyCodeCombo.altKey, keyCodeCombo.keyCode);
	}

	private _encode(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, principal: number): number {
		return (
			((ctrlKey ? 1 : 0) << 0)
			| ((shiftKey ? 1 : 0) << 1)
			| ((altKey ? 1 : 0) << 2)
			| principal << 3
		) >>> 0;
	}
}

export class MacLinuxKeyboardMapper implements IKeyboardMapper {

	/**
	 * Is this the standard US keyboard layout?
	 */
	private readonly _isUSStandard: boolean;
	/**
	 * OS (can be Linux or Macintosh)
	 */
	private readonly _OS: OperatingSystem;
	/**
	 * used only for debug purposes.
	 */
	private readonly _codeInfo: IMacLinuxKeyMapping[];
	/**
	 * Maps ScanCode combos <-> KeyCode combos.
	 */
	private readonly _scanCodeKeyCodeMapper: ScanCodeKeyCodeMapper;
	/**
	 * UI label for a ScanCode.
	 */
	private readonly _scanCodeToLabel: Array<string | null> = [];
	/**
	 * Dispatching string for a ScanCode.
	 */
	private readonly _scanCodeToDispatch: Array<string | null> = [];

	constructor(isUSStandard: boolean, rawMappings: IMacLinuxKeyboardMapping, OS: OperatingSystem) {
		this._isUSStandard = isUSStandard;
		this._OS = OS;
		this._codeInfo = [];
		this._scanCodeKeyCodeMapper = new ScanCodeKeyCodeMapper();
		this._scanCodeToLabel = [];
		this._scanCodeToDispatch = [];

		const _registerIfUnknown = (
			hwCtrlKey: 0 | 1, hwShiftKey: 0 | 1, hwAltKey: 0 | 1, scanCode: ScanCode,
			kbCtrlKey: 0 | 1, kbShiftKey: 0 | 1, kbAltKey: 0 | 1, keyCode: KeyCode,
		): void => {
			this._scanCodeKeyCodeMapper.registerIfUnknown(
				new ScanCodeCombo(hwCtrlKey ? true : false, hwShiftKey ? true : false, hwAltKey ? true : false, scanCode),
				new KeyCodeCombo(kbCtrlKey ? true : false, kbShiftKey ? true : false, kbAltKey ? true : false, keyCode)
			);
		};

		const _registerAllCombos = (_ctrlKey: 0 | 1, _shiftKey: 0 | 1, _altKey: 0 | 1, scanCode: ScanCode, keyCode: KeyCode): void => {
			for (let ctrlKey = _ctrlKey; ctrlKey <= 1; ctrlKey++) {
				for (let shiftKey = _shiftKey; shiftKey <= 1; shiftKey++) {
					for (let altKey = _altKey; altKey <= 1; altKey++) {
						_registerIfUnknown(
							ctrlKey, shiftKey, altKey, scanCode,
							ctrlKey, shiftKey, altKey, keyCode
						);
					}
				}
			}
		};

		// Initialize `_scanCodeToLabel`
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			this._scanCodeToLabel[scanCode] = null;
		}

		// Initialize `_scanCodeToDispatch`
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			this._scanCodeToDispatch[scanCode] = null;
		}

		// Handle immutable mappings
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			const keyCode = IMMUTABLE_CODE_TO_KEY_CODE[scanCode];
			if (keyCode !== -1) {
				_registerAllCombos(0, 0, 0, scanCode, keyCode);
				this._scanCodeToLabel[scanCode] = KeyCodeUtils.toString(keyCode);

				if (keyCode === KeyCode.Unknown || keyCode === KeyCode.Ctrl || keyCode === KeyCode.Meta || keyCode === KeyCode.Alt || keyCode === KeyCode.Shift) {
					this._scanCodeToDispatch[scanCode] = null; // cannot dispatch on this ScanCode
				} else {
					this._scanCodeToDispatch[scanCode] = `[${ScanCodeUtils.toString(scanCode)}]`;
				}
			}
		}

		// Try to identify keyboard layouts where characters A-Z are missing
		// and forcefully map them to their corresponding scan codes if that is the case
		const missingLatinLettersOverride: { [scanCode: string]: IMacLinuxKeyMapping; } = {};

		{
			let producesLatinLetter: boolean[] = [];
			for (let strScanCode in rawMappings) {
				if (rawMappings.hasOwnProperty(strScanCode)) {
					const scanCode = ScanCodeUtils.toEnum(strScanCode);
					if (scanCode === ScanCode.None) {
						continue;
					}
					if (IMMUTABLE_CODE_TO_KEY_CODE[scanCode] !== -1) {
						continue;
					}

					const rawMapping = rawMappings[strScanCode];
					const value = MacLinuxKeyboardMapper.getCharCode(rawMapping.value);

					if (value >= CharCode.a && value <= CharCode.z) {
						const upperCaseValue = CharCode.A + (value - CharCode.a);
						producesLatinLetter[upperCaseValue] = true;
					}
				}
			}

			const _registerLetterIfMissing = (charCode: CharCode, scanCode: ScanCode, value: string, withShift: string): void => {
				if (!producesLatinLetter[charCode]) {
					missingLatinLettersOverride[ScanCodeUtils.toString(scanCode)] = {
						value: value,
						withShift: withShift,
						withAltGr: '',
						withShiftAltGr: ''<commit_msg>Fixes #86400: forcefully => forcibly<commit_after>/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import { CharCode } from 'vs/base/common/charCode';
import { KeyCode, KeyCodeUtils, Keybinding, ResolvedKeybinding, SimpleKeybinding } from 'vs/base/common/keyCodes';
import { OperatingSystem } from 'vs/base/common/platform';
import { IMMUTABLE_CODE_TO_KEY_CODE, IMMUTABLE_KEY_CODE_TO_CODE, ScanCode, ScanCodeBinding, ScanCodeUtils } from 'vs/base/common/scanCode';
import { IKeyboardEvent } from 'vs/platform/keybinding/common/keybinding';
import { IKeyboardMapper } from 'vs/workbench/services/keybinding/common/keyboardMapper';
import { BaseResolvedKeybinding } from 'vs/platform/keybinding/common/baseResolvedKeybinding';

export interface IMacLinuxKeyMapping {
	value: string;
	withShift: string;
	withAltGr: string;
	withShiftAltGr: string;
}

function macLinuxKeyMappingEquals(a: IMacLinuxKeyMapping, b: IMacLinuxKeyMapping): boolean {
	if (!a && !b) {
		return true;
	}
	if (!a || !b) {
		return false;
	}
	return (
		a.value === b.value
		&& a.withShift === b.withShift
		&& a.withAltGr === b.withAltGr
		&& a.withShiftAltGr === b.withShiftAltGr
	);
}

export interface IMacLinuxKeyboardMapping {
	[scanCode: string]: IMacLinuxKeyMapping;
}

export function macLinuxKeyboardMappingEquals(a: IMacLinuxKeyboardMapping | null, b: IMacLinuxKeyboardMapping | null): boolean {
	if (!a && !b) {
		return true;
	}
	if (!a || !b) {
		return false;
	}
	for (let scanCode = 0; scanCode < ScanCode.MAX_VALUE; scanCode++) {
		const strScanCode = ScanCodeUtils.toString(scanCode);
		const aEntry = a[strScanCode];
		const bEntry = b[strScanCode];
		if (!macLinuxKeyMappingEquals(aEntry, bEntry)) {
			return false;
		}
	}
	return true;
}

/**
 * A map from character to key codes.
 * e.g. Contains entries such as:
 *  - '/' => { keyCode: KeyCode.US_SLASH, shiftKey: false }
 *  - '?' => { keyCode: KeyCode.US_SLASH, shiftKey: true }
 */
const CHAR_CODE_TO_KEY_CODE: ({ keyCode: KeyCode; shiftKey: boolean } | null)[] = [];

export class NativeResolvedKeybinding extends BaseResolvedKeybinding<ScanCodeBinding> {

	private readonly _mapper: MacLinuxKeyboardMapper;

	constructor(mapper: MacLinuxKeyboardMapper, os: OperatingSystem, parts: ScanCodeBinding[]) {
		super(os, parts);
		this._mapper = mapper;
	}

	protected _getLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getUILabelForScanCodeBinding(keybinding);
	}

	protected _getAriaLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getAriaLabelForScanCodeBinding(keybinding);
	}

	protected _getElectronAccelerator(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getElectronAcceleratorLabelForScanCodeBinding(keybinding);
	}

	protected _getUserSettingsLabel(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getUserSettingsLabelForScanCodeBinding(keybinding);
	}

	protected _isWYSIWYG(binding: ScanCodeBinding | null): boolean {
		if (!binding) {
			return true;
		}
		if (IMMUTABLE_CODE_TO_KEY_CODE[binding.scanCode] !== -1) {
			return true;
		}
		let a = this._mapper.getAriaLabelForScanCodeBinding(binding);
		let b = this._mapper.getUserSettingsLabelForScanCodeBinding(binding);

		if (!a && !b) {
			return true;
		}
		if (!a || !b) {
			return false;
		}
		return (a.toLowerCase() === b.toLowerCase());
	}

	protected _getDispatchPart(keybinding: ScanCodeBinding): string | null {
		return this._mapper.getDispatchStrForScanCodeBinding(keybinding);
	}
}

interface IScanCodeMapping {
	scanCode: ScanCode;
	value: number;
	withShift: number;
	withAltGr: number;
	withShiftAltGr: number;
}

class ScanCodeCombo {
	public readonly ctrlKey: boolean;
	public readonly shiftKey: boolean;
	public readonly altKey: boolean;
	public readonly scanCode: ScanCode;

	constructor(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, scanCode: ScanCode) {
		this.ctrlKey = ctrlKey;
		this.shiftKey = shiftKey;
		this.altKey = altKey;
		this.scanCode = scanCode;
	}

	public toString(): string {
		return `${this.ctrlKey ? 'Ctrl+' : ''}${this.shiftKey ? 'Shift+' : ''}${this.altKey ? 'Alt+' : ''}${ScanCodeUtils.toString(this.scanCode)}`;
	}

	public equals(other: ScanCodeCombo): boolean {
		return (
			this.ctrlKey === other.ctrlKey
			&& this.shiftKey === other.shiftKey
			&& this.altKey === other.altKey
			&& this.scanCode === other.scanCode
		);
	}

	private getProducedCharCode(mapping: IMacLinuxKeyMapping): string {
		if (!mapping) {
			return '';
		}
		if (this.ctrlKey && this.shiftKey && this.altKey) {
			return mapping.withShiftAltGr;
		}
		if (this.ctrlKey && this.altKey) {
			return mapping.withAltGr;
		}
		if (this.shiftKey) {
			return mapping.withShift;
		}
		return mapping.value;
	}

	public getProducedChar(mapping: IMacLinuxKeyMapping): string {
		const charCode = MacLinuxKeyboardMapper.getCharCode(this.getProducedCharCode(mapping));
		if (charCode === 0) {
			return ' --- ';
		}
		if (charCode >= CharCode.U_Combining_Grave_Accent && charCode <= CharCode.U_Combining_Latin_Small_Letter_X) {
			// combining
			return 'U+' + charCode.toString(16);
		}
		return '  ' + String.fromCharCode(charCode) + '  ';
	}
}

class KeyCodeCombo {
	public readonly ctrlKey: boolean;
	public readonly shiftKey: boolean;
	public readonly altKey: boolean;
	public readonly keyCode: KeyCode;

	constructor(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, keyCode: KeyCode) {
		this.ctrlKey = ctrlKey;
		this.shiftKey = shiftKey;
		this.altKey = altKey;
		this.keyCode = keyCode;
	}

	public toString(): string {
		return `${this.ctrlKey ? 'Ctrl+' : ''}${this.shiftKey ? 'Shift+' : ''}${this.altKey ? 'Alt+' : ''}${KeyCodeUtils.toString(this.keyCode)}`;
	}
}

class ScanCodeKeyCodeMapper {

	/**
	 * ScanCode combination => KeyCode combination.
	 * Only covers relevant modifiers ctrl, shift, alt (since meta does not influence the mappings).
	 */
	private readonly _scanCodeToKeyCode: number[][] = [];
	/**
	 * inverse of `_scanCodeToKeyCode`.
	 * KeyCode combination => ScanCode combination.
	 * Only covers relevant modifiers ctrl, shift, alt (since meta does not influence the mappings).
	 */
	private readonly _keyCodeToScanCode: number[][] = [];

	constructor() {
		this._scanCodeToKeyCode = [];
		this._keyCodeToScanCode = [];
	}

	public registrationComplete(): void {
		// IntlHash and IntlBackslash are rare keys, so ensure they don't end up being the preferred...
		this._moveToEnd(ScanCode.IntlHash);
		this._moveToEnd(ScanCode.IntlBackslash);
	}

	private _moveToEnd(scanCode: ScanCode): void {
		for (let mod = 0; mod < 8; mod++) {
			const encodedKeyCodeCombos = this._scanCodeToKeyCode[(scanCode << 3) + mod];
			if (!encodedKeyCodeCombos) {
				continue;
			}
			for (let i = 0, len = encodedKeyCodeCombos.length; i < len; i++) {
				const encodedScanCodeCombos = this._keyCodeToScanCode[encodedKeyCodeCombos[i]];
				if (encodedScanCodeCombos.length === 1) {
					continue;
				}
				for (let j = 0, len = encodedScanCodeCombos.length; j < len; j++) {
					const entry = encodedScanCodeCombos[j];
					const entryScanCode = (entry >>> 3);
					if (entryScanCode === scanCode) {
						// Move this entry to the end
						for (let k = j + 1; k < len; k++) {
							encodedScanCodeCombos[k - 1] = encodedScanCodeCombos[k];
						}
						encodedScanCodeCombos[len - 1] = entry;
					}
				}
			}
		}
	}

	public registerIfUnknown(scanCodeCombo: ScanCodeCombo, keyCodeCombo: KeyCodeCombo): void {
		if (keyCodeCombo.keyCode === KeyCode.Unknown) {
			return;
		}
		const scanCodeComboEncoded = this._encodeScanCodeCombo(scanCodeCombo);
		const keyCodeComboEncoded = this._encodeKeyCodeCombo(keyCodeCombo);

		const keyCodeIsDigit = (keyCodeCombo.keyCode >= KeyCode.KEY_0 && keyCodeCombo.keyCode <= KeyCode.KEY_9);
		const keyCodeIsLetter = (keyCodeCombo.keyCode >= KeyCode.KEY_A && keyCodeCombo.keyCode <= KeyCode.KEY_Z);

		const existingKeyCodeCombos = this._scanCodeToKeyCode[scanCodeComboEncoded];

		// Allow a scan code to map to multiple key codes if it is a digit or a letter key code
		if (keyCodeIsDigit || keyCodeIsLetter) {
			// Only check that we don't insert the same entry twice
			if (existingKeyCodeCombos) {
				for (let i = 0, len = existingKeyCodeCombos.length; i < len; i++) {
					if (existingKeyCodeCombos[i] === keyCodeComboEncoded) {
						// avoid duplicates
						return;
					}
				}
			}
		} else {
			// Don't allow multiples
			if (existingKeyCodeCombos && existingKeyCodeCombos.length !== 0) {
				return;
			}
		}

		this._scanCodeToKeyCode[scanCodeComboEncoded] = this._scanCodeToKeyCode[scanCodeComboEncoded] || [];
		this._scanCodeToKeyCode[scanCodeComboEncoded].unshift(keyCodeComboEncoded);

		this._keyCodeToScanCode[keyCodeComboEncoded] = this._keyCodeToScanCode[keyCodeComboEncoded] || [];
		this._keyCodeToScanCode[keyCodeComboEncoded].unshift(scanCodeComboEncoded);
	}

	public lookupKeyCodeCombo(keyCodeCombo: KeyCodeCombo): ScanCodeCombo[] {
		const keyCodeComboEncoded = this._encodeKeyCodeCombo(keyCodeCombo);
		const scanCodeCombosEncoded = this._keyCodeToScanCode[keyCodeComboEncoded];
		if (!scanCodeCombosEncoded || scanCodeCombosEncoded.length === 0) {
			return [];
		}

		let result: ScanCodeCombo[] = [];
		for (let i = 0, len = scanCodeCombosEncoded.length; i < len; i++) {
			const scanCodeComboEncoded = scanCodeCombosEncoded[i];

			const ctrlKey = (scanCodeComboEncoded & 0b001) ? true : false;
			const shiftKey = (scanCodeComboEncoded & 0b010) ? true : false;
			const altKey = (scanCodeComboEncoded & 0b100) ? true : false;
			const scanCode: ScanCode = (scanCodeComboEncoded >>> 3);

			result[i] = new ScanCodeCombo(ctrlKey, shiftKey, altKey, scanCode);
		}
		return result;
	}

	public lookupScanCodeCombo(scanCodeCombo: ScanCodeCombo): KeyCodeCombo[] {
		const scanCodeComboEncoded = this._encodeScanCodeCombo(scanCodeCombo);
		const keyCodeCombosEncoded = this._scanCodeToKeyCode[scanCodeComboEncoded];
		if (!keyCodeCombosEncoded || keyCodeCombosEncoded.length === 0) {
			return [];
		}

		let result: KeyCodeCombo[] = [];
		for (let i = 0, len = keyCodeCombosEncoded.length; i < len; i++) {
			const keyCodeComboEncoded = keyCodeCombosEncoded[i];

			const ctrlKey = (keyCodeComboEncoded & 0b001) ? true : false;
			const shiftKey = (keyCodeComboEncoded & 0b010) ? true : false;
			const altKey = (keyCodeComboEncoded & 0b100) ? true : false;
			const keyCode: KeyCode = (keyCodeComboEncoded >>> 3);

			result[i] = new KeyCodeCombo(ctrlKey, shiftKey, altKey, keyCode);
		}
		return result;
	}

	public guessStableKeyCode(scanCode: ScanCode): KeyCode {
		if (scanCode >= ScanCode.Digit1 && scanCode <= ScanCode.Digit0) {
			// digits are ok
			switch (scanCode) {
				case ScanCode.Digit1: return KeyCode.KEY_1;
				case ScanCode.Digit2: return KeyCode.KEY_2;
				case ScanCode.Digit3: return KeyCode.KEY_3;
				case ScanCode.Digit4: return KeyCode.KEY_4;
				case ScanCode.Digit5: return KeyCode.KEY_5;
				case ScanCode.Digit6: return KeyCode.KEY_6;
				case ScanCode.Digit7: return KeyCode.KEY_7;
				case ScanCode.Digit8: return KeyCode.KEY_8;
				case ScanCode.Digit9: return KeyCode.KEY_9;
				case ScanCode.Digit0: return KeyCode.KEY_0;
			}
		}

		// Lookup the scanCode with and without shift and see if the keyCode is stable
		const keyCodeCombos1 = this.lookupScanCodeCombo(new ScanCodeCombo(false, false, false, scanCode));
		const keyCodeCombos2 = this.lookupScanCodeCombo(new ScanCodeCombo(false, true, false, scanCode));
		if (keyCodeCombos1.length === 1 && keyCodeCombos2.length === 1) {
			const shiftKey1 = keyCodeCombos1[0].shiftKey;
			const keyCode1 = keyCodeCombos1[0].keyCode;
			const shiftKey2 = keyCodeCombos2[0].shiftKey;
			const keyCode2 = keyCodeCombos2[0].keyCode;
			if (keyCode1 === keyCode2 && shiftKey1 !== shiftKey2) {
				// This looks like a stable mapping
				return keyCode1;
			}
		}

		return -1;
	}

	private _encodeScanCodeCombo(scanCodeCombo: ScanCodeCombo): number {
		return this._encode(scanCodeCombo.ctrlKey, scanCodeCombo.shiftKey, scanCodeCombo.altKey, scanCodeCombo.scanCode);
	}

	private _encodeKeyCodeCombo(keyCodeCombo: KeyCodeCombo): number {
		return this._encode(keyCodeCombo.ctrlKey, keyCodeCombo.shiftKey, keyCodeCombo.altKey, keyCodeCombo.keyCode);
	}

	private _encode(ctrlKey: boolean, shiftKey: boolean, altKey: boolean, principal: number): number {
		return (
			((ctrlKey ? 1 : 0) << 0)
			| ((shiftKey ? 1 : 0) << 1)
			| ((altKey ? 1 : 0) << 2)
			| principal << 3
		) >>> 0;
	}
}

export class MacLinuxKeyboardMapper implements IKeyboardMapper {

	/**
	 * Is this the standard US keyboard layout?
	 */
	private readonly _isUSStandard: boolean;
	/**
	 * OS (can be Linux or Macintosh)
	 */
	private readonly _OS: OperatingSystem;
	/**
	 * used only for debug purposes.
	 */
	private readonly _codeInfo: IMacLinuxKeyMapping[];
	/**
	 * Maps ScanCode combos <-> KeyCode combos.
	 */
	private readonly _scanCodeKeyCodeMapper: ScanCodeKeyCodeMapper;
	/**
	 * UI label for a ScanCode.
	 */
	private readonly _scanCodeToLabel: Array<string | null> = [];
	/**
	 * Dispatching string for a ScanCode.
	 */
	private readonly _scanCodeToDispatch: Array<string | null> = [];

	constructor(isUSStandard: boolean, rawMappings: IMacLinuxKeyboardMapping, OS: OperatingSystem) {
		this._isUSStandard = isUSStandard;
		this._OS = OS;
		this._codeInfo = [];
		this._scanCodeKeyCodeMapper = new ScanCodeKeyCodeMapper();
		this._scanCodeToLabel = [];
		this._scanCodeToDispatch = [];

		const _registerIfUnknown = (
			hwCtrlKey: 0 | 1, hwShiftKey: 0 | 1, hwAltKey: 0 | 1, scanCode: ScanCode,
			kbCtrlKey: 0 | 1, kbShiftKey: 0 | 1, kbAltKey: 0 | 1, keyCode: KeyCode,
		): void => {
			this._scanCodeKeyCodeMapper.registerIfUnknown(
				new ScanCodeCombo(hwCtrlKey ? true : false, hwShiftKey ? true : false, hwAltKey ? true : false, scanCode),
				new KeyCodeCombo(kbCtrlKey ? true : false, kbShiftKey ? true : false, kbAltKey ? true : false, keyCode)
			);
		};

		const _registerAllCombos = (_ctrlKey: 0 | 1, _shiftKey: 0 | 1, _altKey: 0 | 1, scanCode: ScanCode, keyCode: KeyCode): void => {
			for (let ctrlKey = _ctrlKey; ctrlKey <= 1; ctrlKey++) {
				for (let shiftKey = _shiftKey; shiftKey <= 1; shiftKey++) {
					for (let altKey = _altKey; altKey <= 1; altKey++) {
						_registerIfUnknown(
							ctrlKey, shiftKey, altKey, scanCode,
							ctrlKey, shiftKey, altKey, keyCode
						);
					}
				}
			}
		};

		// Initialize `_scanCodeToLabel`
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			this._scanCodeToLabel[scanCode] = null;
		}

		// Initialize `_scanCodeToDispatch`
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			this._scanCodeToDispatch[scanCode] = null;
		}

		// Handle immutable mappings
		for (let scanCode = ScanCode.None; scanCode < ScanCode.MAX_VALUE; scanCode++) {
			const keyCode = IMMUTABLE_CODE_TO_KEY_CODE[scanCode];
			if (keyCode !== -1) {
				_registerAllCombos(0, 0, 0, scanCode, keyCode);
				this._scanCodeToLabel[scanCode] = KeyCodeUtils.toString(keyCode);

				if (keyCode === KeyCode.Unknown || keyCode === KeyCode.Ctrl || keyCode === KeyCode.Meta || keyCode === KeyCode.Alt || keyCode === KeyCode.Shift) {
					this._scanCodeToDispatch[scanCode] = null; // cannot dispatch on this ScanCode
				} else {
					this._scanCodeToDispatch[scanCode] = `[${ScanCodeUtils.toString(scanCode)}]`;
				}
			}
		}

		// Try to identify keyboard layouts where characters A-Z are missing
		// and forcibly map them to their corresponding scan codes if that is the case
		const missingLatinLettersOverride: { [scanCode: string]: IMacLinuxKeyMapping; } = {};

		{
			let producesLatinLetter: boolean[] = [];
			for (let strScanCode in rawMappings) {
				if (rawMappings.hasOwnProperty(strScanCode)) {
					const scanCode = ScanCodeUtils.toEnum(strScanCode);
					if (scanCode === ScanCode.None) {
						continue;
					}
					if (IMMUTABLE_CODE_TO_KEY_CODE[scanCode] !== -1) {
						continue;
					}

					const rawMapping = rawMappings[strScanCode];
					const value = MacLinuxKeyboardMapper.getCharCode(rawMapping.value);

					if (value >= CharCode.a && value <= CharCode.z) {
						const upperCaseValue = CharCode.A + (value - CharCode.a);
						producesLatinLetter[upperCaseValue] = true;
					}
				}
			}

			const _registerLetterIfMissing = (charCode: CharCode, scanCode: ScanCode, value: string, withShift: string): void => {
				if (!producesLatinLetter[charCode]) {
					missingLatinLettersOverride[ScanCodeUtils.toString(scanCode)] = {
						value: value,
						withShift: withShift,
						withAltGr: '',
						withShiftAltGr: ''
{'fraction_non_alphanumeric': 0.12977798799775328, 'fraction_numerical': 0.00795222751056848, 'mean_word_length': 4.007846039970392, 'pattern_counts': {'":': 0, '<': 69, '<?xml version=': 0, '>': 60, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5712786', 'n_tokens_mistral': 12498, 'n_tokens_neox': 11074, 'n_words': 2539}