Feature: different MenuSearch modes

Fluxbox now supports three MenuSearch modes:

* NoWhere - essentially "disabling" the menu search.
* Somewhere - the search string matches somewhere.
* ItemStart - the search string matches at the start of a menu item.

The default value is "ItemStart", just in the good old times. As long as
this feature is not configurable via the menu it would irritate users
with distinct muscle memory who type without thinking OR checking the
visual feedback: they would trigger items they did not intent to trigger
after years of the old behavior.

Once this feature get's an entry in the config menu the default value
might change.

8 files changed, 298 insertions, 149 deletions

diff --git a/src/FbTk/Makemodule.am b/src/FbTk/Makemodule.am
index 57f70f2..3433429 100644
--- a/src/FbTk/Makemodule.am
+++ b/src/FbTk/Makemodule.am
@@ -102,6 +102,8 @@ libFbTk_a_SOURCES = \
         src/FbTk/Menu.hh \
         src/FbTk/MenuItem.cc \
         src/FbTk/MenuItem.hh \
+        src/FbTk/MenuSearch.hh \
+        src/FbTk/MenuSearch.cc \
         src/FbTk/MenuSeparator.cc \
         src/FbTk/MenuSeparator.hh \
         src/FbTk/MenuTheme.cc \
diff --git a/src/FbTk/Menu.cc b/src/FbTk/Menu.cc
index 539c72c..cfbf049 100644
--- a/src/FbTk/Menu.cc
+++ b/src/FbTk/Menu.cc
@@ -69,143 +69,11 @@ void renderMenuPixmap(Pixmap& pm, FbTk::FbWindow* win, int width, int height, co
     }
 }
 
-
-// finds 'pattern' in 'text', case insensitive.
-// returns position or std::string::npos if not found.
-//
-// implements Boyer–Moore–Horspool
-size_t search_string(const std::string& text, const std::string& pattern) {
-
-    if (pattern.empty()) {
-        return 0;
-    }
-    if (text.empty() || pattern.size() > text.size()) {
-        return std::string::npos;
-    }
-
-    size_t t;
-    size_t tlen = text.size();
-
-    // simple case, no need to be too clever
-    if (pattern.size() == 1) {
-        int b = std::tolower(pattern[0]);
-        for (t = 0; t < tlen; t++) {
-            if (b == std::tolower(text[t])) {
-                return t;
-            }
-        }
-        return std::string::npos;
-    }
-
-
-    size_t plast = pattern.size() - 1;
-    size_t p;
-
-    // prepare skip-table
-    //
-    size_t skip[256];
-    for (p = 0; p < sizeof(skip)/sizeof(skip[0]); p++) {
-        skip[p] = plast + 1;
-    }
-    for (p = 0; p < plast; p++) {
-        skip[std::tolower(pattern[p])] = plast - p;
-    }
-
-    // match
-    for (t = 0; t + plast < tlen; ) {
-        for (p = plast; std::tolower(text[t+p]) == std::tolower(pattern[p]); p--) {
-            if (p == 0) {
-                return t+p;
-            }
-        }
-        t += skip[std::tolower(text[t+p])];
-    }
-
-    return std::string::npos;
-}
-
 } // end of anonymous namespace
 
 
 namespace FbTk {
 
-// a small helper which applies search operations on a list of MenuItems*.
-// the former incarnation of this class was FbTk::TypeAhead in combination with
-// the now non-existent FbTk::SearchResults, but the complexity of these
-// are not needed for our use case. as a bonus we have less lose parts
-// flying around.
-class FbTk::Menu::TypeSearch {
-public:
-    TypeSearch(std::vector<FbTk::MenuItem*>& items) : m_items(items) { }
-
-    size_t size() const { return pattern.size(); }
-    void clear() { pattern.clear(); }
-    void add(char c) { pattern.push_back(c); }
-    void backspace() {
-        size_t s = pattern.size();
-        if (s > 0) {
-            pattern.erase(s - 1, 1);
-        }
-    }
-
-    // is 'pattern' matching something?
-    bool has_match() {
-        size_t l = m_items.size();
-        size_t i;
-        for (i = 0; i < l; i++) {
-            if (!m_items[i]->isEnabled())
-                continue;
-            if (search_string(m_items[i]->iTypeString(), pattern) != std::string::npos) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    // would 'the_pattern' match something?
-    bool would_match(const std::string& the_pattern) {
-        size_t l = m_items.size();
-        size_t i;
-        for (i = 0; i < l; i++) {
-            if (!m_items[i]->isEnabled())
-                continue;
-            if (search_string(m_items[i]->iTypeString(), the_pattern) != std::string::npos) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    size_t num_matches() {
-        size_t l = m_items.size();
-        size_t i, n;
-        for (i = 0, n = 0; i < l; i++) {
-            if (!m_items[i]->isEnabled())
-                continue;
-            if (search_string(m_items[i]->iTypeString(), pattern) != std::string::npos) {
-                n++;
-            }
-        }
-        return n;
-    }
-
-
-    // returns true if m_text matches against m_items[i] and stores
-    // the position where it matches in the string
-    bool get_match(size_t i, size_t& idx) {
-        if (i > m_items.size()) {
-            return false;
-        }
-        idx = search_string(m_items[i]->iTypeString(), pattern);
-        return idx != std::string::npos;
-    }
-
-    std::string pattern;
-private:
-    const std::vector<FbTk::MenuItem*>& m_items;
-};
-
-
 
 Menu* s_shown = 0; // if there's a menu open at all
 Menu* s_focused = 0; // holds currently focused menu
@@ -250,7 +118,7 @@ Menu::Menu(FbTk::ThemeProxy<MenuTheme> &tm, ImageControl &imgctrl):
     m_internal_menu = false;
     m_state.moving = m_state.closing = m_state.torn = m_state.visible = false;
 
-    m_search.reset(new TypeSearch(m_items));
+    m_search.reset(new MenuSearch(m_items));
 
     m_x_move = m_y_move = 0;
     m_which_sub = -1;
diff --git a/src/FbTk/Menu.hh b/src/FbTk/Menu.hh
index 39440a8..8bb5fdd 100644
--- a/src/FbTk/Menu.hh
+++ b/src/FbTk/Menu.hh
@@ -37,9 +37,10 @@
 namespace FbTk {
 
 template <typename T> class Command;
+template <typename T> class RefCount;
 class MenuItem;
+class MenuSearch;
 class ImageControl;
-template <typename T> class RefCount;
 
 ///   Base class for menus
 class Menu: public FbTk::EventHandler, FbTk::FbWindowRenderer {
@@ -187,10 +188,8 @@ private:
 
     Menu *m_parent;
 
-    class TypeSearch;
-
-    std::vector<MenuItem *>   m_items;
-    std::auto_ptr<TypeSearch> m_search;
+    std::vector<MenuItem*>    m_items;
+    std::auto_ptr<MenuSearch> m_search;
 
     struct State {
         bool moving;
diff --git a/src/FbTk/MenuSearch.cc b/src/FbTk/MenuSearch.cc
new file mode 100644
index 0000000..da903f4
--- /dev/null
+++ b/src/FbTk/MenuSearch.cc
@@ -0,0 +1,221 @@
+#include "MenuSearch.hh"
+#include "MenuItem.hh"
+#include "StringUtil.hh"
+#include "Resource.hh"
+
+namespace {
+
+size_t search_str_nowhere(const std::string& text, const std::string& pattern) {
+    return std::string::npos;
+}
+
+// finds 'pattern' at beginning of 'text'
+size_t search_str_textstart(const std::string& text, const std::string& pattern) {
+
+    size_t l = std::min(text.size(), pattern.size());
+    if (l == 0) {
+        return std::string::npos;
+    }
+
+    size_t i;
+    for (i = l; i > 0; i--) {
+        if (std::tolower(text[i-1]) != std::tolower(pattern[i-1])) {
+            return std::string::npos;
+        }
+    }
+
+    return i;
+}
+
+// finds 'pattern' in 'text', case insensitive.
+// returns position or std::string::npos if not found.
+//
+// implements Boyer–Moore–Horspool
+size_t search_str_bmh(const std::string& text, const std::string& pattern) {
+
+    if (pattern.empty()) {
+        return 0;
+    }
+    if (text.empty() || pattern.size() > text.size()) {
+        return std::string::npos;
+    }
+
+    size_t t;
+    size_t tlen = text.size();
+
+    // simple case, no need to be too clever
+    if (pattern.size() == 1) {
+        int b = std::tolower(pattern[0]);
+        for (t = 0; t < tlen; t++) {
+            if (b == std::tolower(text[t])) {
+                return t;
+            }
+        }
+        return std::string::npos;
+    }
+
+
+    size_t plast = pattern.size() - 1;
+    size_t p;
+
+    // prepare skip-table
+    //
+    size_t skip[256];
+    for (p = 0; p < sizeof(skip)/sizeof(skip[0]); p++) {
+        skip[p] = plast + 1;
+    }
+    for (p = 0; p < plast; p++) {
+        skip[std::tolower(pattern[p])] = plast - p;
+    }
+
+    // match
+    for (t = 0; t + plast < tlen; ) {
+        for (p = plast; std::tolower(text[t+p]) == std::tolower(pattern[p]); p--) {
+            if (p == 0) {
+                return t+p;
+            }
+        }
+        t += skip[std::tolower(text[t+p])];
+    }
+
+    return std::string::npos;
+}
+
+
+// actually search function, depends on Mode
+size_t (*search_str)(const std::string&, const std::string&) = search_str_textstart;
+
+} // anonymous
+
+
+
+namespace FbTk {
+
+
+void MenuSearch::setMode(MenuSearch::Mode m) {
+    if (m == NOWHERE) {
+        search_str = search_str_nowhere;
+    } else if (m == SOMEWHERE) {
+        search_str = search_str_bmh;
+    } else {
+        search_str = search_str_textstart;
+    }
+}
+
+
+
+MenuSearch::MenuSearch(const std::vector<FbTk::MenuItem*>& items) : 
+    m_items(items) {
+}
+
+size_t MenuSearch::size() const { 
+    return pattern.size();
+}
+
+void MenuSearch::clear() { 
+    pattern.clear();
+}
+
+void MenuSearch::add(char c) {
+    pattern.push_back(c);
+}
+
+void MenuSearch::backspace() {
+    size_t s = pattern.size();
+    if (s > 0) {
+        pattern.erase(s - 1, 1);
+    }
+}
+
+// is 'pattern' matching something?
+bool MenuSearch::has_match() {
+    size_t l = m_items.size();
+    size_t i;
+    for (i = 0; i < l; i++) {
+        if (!m_items[i]->isEnabled())
+            continue;
+        if (search_str(m_items[i]->iTypeString(), pattern) != std::string::npos) {
+            return true;
+        }
+    }
+    return false;
+}
+
+// would 'the_pattern' match something?
+bool MenuSearch::would_match(const std::string& the_pattern) {
+    size_t l = m_items.size();
+    size_t i;
+    for (i = 0; i < l; i++) {
+        if (!m_items[i]->isEnabled())
+            continue;
+        if (search_str(m_items[i]->iTypeString(), the_pattern) != std::string::npos) {
+            return true;
+        }
+    }
+    return false;
+}
+
+size_t MenuSearch::num_matches() {
+    size_t l = m_items.size();
+    size_t i, n;
+    for (i = 0, n = 0; i < l; i++) {
+        if (!m_items[i]->isEnabled())
+            continue;
+        if (search_str(m_items[i]->iTypeString(), pattern) != std::string::npos) {
+            n++;
+        }
+    }
+    return n;
+}
+
+
+// returns true if m_text matches against m_items[i] and stores
+// the position where it matches in the string. an empty
+// 'pattern' always matches
+bool MenuSearch::get_match(size_t i, size_t& idx) {
+    if (i > m_items.size()) {
+        return false;
+    }
+
+    if (pattern.empty())
+        return true;
+
+    idx = search_str(m_items[i]->iTypeString(), pattern);
+    return idx != std::string::npos;
+}
+
+
+
+
+//
+// resource-implementation related
+
+template<>
+std::string FbTk::Resource<FbTk::MenuSearch::Mode>::getString() const {
+
+    switch (m_value) {
+    case FbTk::MenuSearch::NOWHERE:
+        return "nowhere";
+    case FbTk::MenuSearch::SOMEWHERE:
+        return "somewhere";
+    default:
+        return "itemstart";
+    };
+}
+
+template<>
+void FbTk::Resource<FbTk::MenuSearch::Mode>::setFromString(const char *strval) {
+
+    std::string val = FbTk::StringUtil::toLower(strval);
+    if (val == "nowhere") {
+        m_value = FbTk::MenuSearch::NOWHERE;
+    } else if (val == "somewhere") {
+        m_value = FbTk::MenuSearch::SOMEWHERE;
+    } else {
+        setDefaultValue();
+    }
+
+    std::cerr << "** " << val << " " << m_value << "\n";
+}
+
+}
diff --git a/src/FbTk/MenuSearch.hh b/src/FbTk/MenuSearch.hh
new file mode 100644
index 0000000..d642929
--- /dev/null
+++ b/src/FbTk/MenuSearch.hh
@@ -0,0 +1,60 @@
+#ifndef _MENU_SEARCH_HH_
+#define _MENU_SEARCH_HH_
+
+#include <vector>
+#include <string>
+#include <cstddef>
+
+namespace FbTk {
+
+class MenuItem;
+
+
+// a small helper which applies search operations on a list of MenuItems*.
+// the former incarnation of this class was FbTk::TypeAhead in combination with
+// the now non-existent FbTk::SearchResults, but the complexity of these
+// are not needed for our use case. as a bonus we have less lose parts
+// flying around.
+
+class MenuSearch {
+public:
+
+    enum Mode {
+        NOWHERE,
+        ITEMSTART,
+        SOMEWHERE,
+
+        DEFAULT = ITEMSTART
+    };
+
+    static void setMode(Mode m);
+
+
+    MenuSearch(const std::vector<FbTk::MenuItem*>& items);
+
+    size_t size() const;
+    void clear();
+    void add(char c);
+    void backspace();
+
+    // is 'pattern' matching something?
+    bool has_match();
+
+    // would 'the_pattern' match something?
+    bool would_match(const std::string& the_pattern);
+
+    size_t num_matches();
+
+    // returns true if m_text matches against m_items[i] and stores
+    // the position where it matches in the string
+    bool get_match(size_t i, size_t& idx);
+
+    std::string pattern;
+private:
+    const std::vector<FbTk::MenuItem*>& m_items;
+};
+
+}
+
+
+#endif
diff --git a/src/FbTk/Resource.cc b/src/FbTk/Resource.cc
index 4be85de..af0c4c2 100644
--- a/src/FbTk/Resource.cc
+++ b/src/FbTk/Resource.cc
@@ -25,11 +25,7 @@
 #include "StringUtil.hh"
 
 #include <iostream>
-#ifdef HAVE_CASSERT
-  #include <cassert>
-#else
-  #include <assert.h>
-#endif
+#include <cassert>
 
 using std::cerr;
 using std::endl;
@@ -38,9 +34,9 @@ using std::string;
 namespace FbTk {
 
 ResourceManager::ResourceManager(const char *filename, bool lock_db) :
- m_db_lock(0),
- m_database(0),
- m_filename(filename ? filename : "")
+    m_db_lock(0),
+    m_database(0),
+    m_filename(filename ? filename : "")
 {
     static bool xrm_initialized = false;
     if (!xrm_initialized) {
diff --git a/src/fluxbox.cc b/src/fluxbox.cc
index 8b8b26c..7b73360 100644
--- a/src/fluxbox.cc
+++ b/src/fluxbox.cc
@@ -252,6 +252,7 @@ Fluxbox::Config::Config(FbTk::ResourceManager& rm, const std::string& path) :
     slit_file(rm, path + "/slitlist", "session.slitlistFile", "Session.SlitlistFile"),
     apps_file(rm, path + "/apps", "session.appsFile", "Session.AppsFile"),
     tabs_attach_area(rm, ATTACH_AREA_WINDOW, "session.tabsAttachArea", "Session.TabsAttachArea"),
+    menusearch(rm, FbTk::MenuSearch::DEFAULT, "session.menuSearch", "Session.MenuSearch"),
     cache_life(rm, 5, "session.cacheLife", "Session.CacheLife"),
     cache_max(rm, 200, "session.cacheMax", "Session.CacheMax"),
     auto_raise_delay(rm, 250, "session.autoRaiseDelay", "Session.AutoRaiseDelay") {
@@ -360,7 +361,7 @@ Fluxbox::Fluxbox(int argc, char **argv,
     // Note: this needs to be done before creating screens
     m_key.reset(new Keys);
     m_key->reconfigure();
-
+    FbTk::MenuSearch::setMode(*m_config.menusearch);
 
     unsigned int opts = OPT_SLIT|OPT_TOOLBAR;
     vector<int> screens;
@@ -541,7 +542,6 @@ void Fluxbox::eventLoop() {
         } else {
             FbTk::Timer::updateTimers(ConnectionNumber(disp));
         }
-
     }
 }
 
@@ -862,7 +862,7 @@ void Fluxbox::handleClientMessage(XClientMessageEvent &ce) {
         atom = XGetAtomName(FbTk::App::instance()->display(), ce.message_type);
 
     fbdbg<<__FILE__<<"("<<__LINE__<<"): ClientMessage. data.l[0]=0x"<<hex<<ce.data.l[0]<<
-        "  message_type=0x"<<ce.message_type<<dec<<" = \""<<atom<<"\""<<endl;
+        "  message_type=0x"<<ce.message_type<<dec<<" = \""<<atom<<"\""<<endl;
 
     if (ce.message_type && atom) XFree((char *) atom);
 #endif // DEBUG
@@ -1266,6 +1266,7 @@ void Fluxbox::real_reconfigure() {
     STLUtil::forAll(m_screens, mem_fun(&BScreen::reconfigure));
     m_key->reconfigure();
     STLUtil::forAll(m_atomhandler, mem_fun(&AtomHandler::reconfigure));
+    FbTk::MenuSearch::setMode(*m_config.menusearch);
 }
 
 BScreen *Fluxbox::findScreen(int id) {
diff --git a/src/fluxbox.hh b/src/fluxbox.hh
index df0335a..2d2e670 100644
--- a/src/fluxbox.hh
+++ b/src/fluxbox.hh
@@ -29,6 +29,7 @@
 #include "FbTk/Resource.hh"
 #include "FbTk/Timer.hh"
 #include "FbTk/Signal.hh"
+#include "FbTk/MenuSearch.hh"
 
 #include "AttentionNoticeHandler.hh"
 
@@ -251,6 +252,7 @@ private:
         FbTk::Resource<std::string> apps_file;
 
         FbTk::Resource<TabsAttachArea> tabs_attach_area;
+        FbTk::Resource<FbTk::MenuSearch::Mode> menusearch;
         FbTk::Resource<unsigned int>   cache_life;
         FbTk::Resource<unsigned int>   cache_max;
         FbTk::Resource<time_t>         auto_raise_delay;