Ghidra is a software reverse engineering (SRE) framework
/* ###
* IP: GHIDRA
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package docking.widgets;
import java.awt.event.InputEvent;
import java.awt.event.KeyEvent;
import java.util.function.Predicate;
import org.apache.commons.lang3.Strings;
/**
* A class that holds the logic and state for finding matching rows in a widget when a user types
* in the widget. This class was designed for row-based widgets, such as tables and lists.
*/
public abstract class AutoLookup {
public static final long KEY_TYPING_TIMEOUT = 800;
private static final int MAX_SEARCH_ROWS = 50000;
private long keyTimeout = KEY_TYPING_TIMEOUT;
private Predicate<Long> keyTimeoutPredicate = elapsedTime -> elapsedTime > keyTimeout;
private AutoLookupItem lastLookup;
private int lookupColumn = 0;
/**
* Returns the currently selected row
* @return the row
*/
public abstract int getCurrentRow();
/**
* Returns the total number of rows
* @return the row count
*/
public abstract int getRowCount();
/**
* Returns a string representation of the item at the given row and column. The text
* should match what the user sees.
*
* @param row the row
* @param col the column
* @return the text
*/
public abstract String getValueString(int row, int col);
/**
* Returns true if the given column is sorted. This class will use a binary search if the
* given column is sorted. Otherwise, a brute-force search will be used.
*
* @param column the column
* @return true if sorted
*/
public abstract boolean isSorted(int column);
/**
* A method that subclasses can override to affect whether this class uses a binary search
* for a particular column
* @param column the column
* @return true if the binary search algorithm will work on the given column
*/
protected boolean canBinarySearchColumn(int column) {
return isSorted(column);
}
/**
* Returns true if the currently sorted column is sorted ascending. This is used in
* conjunction with {@link #isSorted(int)}. If that method returns false, then this method
* will not be called.
*
* @return true if sorted ascending
*/
public abstract boolean isSortedAscending();
/**
* This method will be called when a match for the call to {@link #keyTyped(KeyEvent)} is
* found
*
* @param row the matching row
*/
public abstract void matchFound(int row);
/**
* Sets the delay between keystrokes after which each keystroke is considered a new lookup
* @param timeout the timeout
*/
public void setTimeout(long timeout) {
keyTimeout = timeout;
lastLookup = null;
}
/**
* Sets the column that is searched when a lookup is performed
* @param column the column
*/
public void setColumn(int column) {
this.lookupColumn = column;
lastLookup = null;
}
/**
* Sets the logic for deciding whether the elapsed time between keystrokes is enough to
* trigger a new auto lookup or to continue with the previous match.
*
* <p>This method is intended for tests that need precise control over the timeout mechanism.
*
*
* @param p the predicate that takes the amount of elapsed time
* @see #setTimeout(long)
*/
public void setTimeoutPredicate(Predicate<Long> p) {
this.keyTimeoutPredicate = p;
}
/**
* Clients call this method when the user types keys
*
* @param e the key event
*/
public void keyTyped(KeyEvent e) {
if (getRowCount() == 0) {
return;
}
AutoLookupItem lookup = lastLookup;
if (lookup == null) {
lookup = new AutoLookupItem();
}
lookup.keyTyped(e);
if (lookup.shouldSkip()) {
return;
}
int row = lookupText(lookup.getText());
lookup.setFoundMatch(row >= 0);
if (row >= 0) {
matchFound(row);
}
lastLookup = lookup;
}
private int lookupText(String text) {
if (text == null) {
return -1;
}
int row = getCurrentRow();
if (row >= 0 && row < getRowCount() - 1) {
if (text.length() == 1) {
// fresh search; ignore the current row, could be from a previous match
++row;
}
int col = lookupColumn;
if (textMatches(text, row, col)) {
return row;
}
}
if (canBinarySearchColumn(lookupColumn)) {
return autoLookupBinary(text);
}
return autoLookupLinear(text);
}
private boolean textMatches(String text, int row, int col) {
String value = getValueString(row, col);
return Strings.CI.startsWith(value, text);
}
private boolean isIgnorableKeyEvent(KeyEvent event) {
// ignore modified keys, except for SHIFT
if (!isUnmodifiedOrShift(event.getModifiersEx())) {
return true;
}
if (event.isActionKey() || event.getKeyChar() == KeyEvent.CHAR_UNDEFINED ||
Character.isISOControl(event.getKeyChar())) {
return true;
}
return false;
}
private boolean isUnmodifiedOrShift(int modifiers) {
if (modifiers == 0) {
return true;
}
int shift = InputEvent.SHIFT_DOWN_MASK;
return (modifiers | shift) != shift;
}
private int autoLookupLinear(String text) {
int max = MAX_SEARCH_ROWS;
int rows = getRowCount();
int start = getCurrentRow();
int counter = 0;
int col = lookupColumn;
// first search from the current row until the last row
for (int i = start + 1; i < rows && counter < max; i++, counter++) {
if (textMatches(text, i, col)) {
return i;
}
}
// then wrap the search to be from the beginning to the current row
for (int i = 0; i < start && counter < max; i++, counter++) {
if (textMatches(text, i, col)) {
return i;
}
}
return -1;
}
private int autoLookupBinary(String text) {
int index = binarySearch(text);
int col = lookupColumn;
if (textMatches(text, index, col)) {
return index;
}
if (index - 1 >= 0) {
if (textMatches(text, index - 1, col)) {
return index - 1;
}
}
if (index + 1 < getRowCount()) {
if (textMatches(text, index + 1, col)) {
return index + 1;
}
}
return -1;
}
private int binarySearch(String text) {
int sortedOrder = 1;
// if sorted descending, then reverse the search direction and change the lookup text to
// so that a match will come after the range we seek, which is before the desired text
// when sorted in reverse
if (!isSortedAscending()) {
sortedOrder = -1;
int lastPos = text.length() - 1;
char lastChar = text.charAt(lastPos);
++lastChar;
text = text.substring(0, lastPos) + lastChar;
}
int min = 0;
int rows = getRowCount();
int max = rows - 1;
int col = lookupColumn;
while (min < max) {
// divide by 2; preserve the sign to prevent possible overflow issue
int mid = (min + max) >>> 1;
String value = getValueString(mid, col);
int compare = text.compareToIgnoreCase(value);
compare *= sortedOrder;
if (compare < 0) {
max = mid - 1;
}
else if (compare > 0) {
min = mid + 1;
}
else { // exact match
return mid;
}
}
return min;
}
private class AutoLookupItem {
private long lastTime;
private String text;
private boolean foundPreviousMatch;
private boolean skip;
void keyTyped(KeyEvent e) {
skip = false;
if (isIgnorableKeyEvent(e)) {
skip = true;
return;
}
String eventChar = Character.toString(e.getKeyChar());
long when = e.getWhen();
long elapsed = when - lastTime;
boolean didTimeout = keyTimeoutPredicate.test(elapsed);
if (didTimeout) {
text = eventChar;
}
else {
text += eventChar;
if (!foundPreviousMatch) {
// The given character is being added to the previous search. If that search
// was fruitless, then so too will be this one, since we use a
// 'starts with' match.
skip = true;
when = lastTime; // don't save time if no match found; trigger a timeout
}
}
lastTime = when;
}
void setFoundMatch(boolean foundMatch) {
foundPreviousMatch = foundMatch;
}
String getText() {
return text;
}
boolean shouldSkip() {
return skip;
}
}
}