'Find-as-you-type'-search in dartdoc/apidoc.

pkg/dartdoc/search.dart

Index: pkg/dartdoc/search.dart
diff --git a/pkg/dartdoc/search.dart b/pkg/dartdoc/search.dart
new file mode 100644
index 0000000000000000000000000000000000000000..130b8023d3e5dcd14c8a0b61c6a0256cde93ac25
--- /dev/null
+++ b/pkg/dartdoc/search.dart
@@ -0,0 +1,512 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/**
+ * [SearchText] represent the search field text. The text is viewed in three
+ * ways: [text] holds the original search text, used for performing
+ * case-sensitive matches, [lowerCase] holds the lower-case search text, used
+ * for performing case-insenstive matches, [camelCase] holds a camel-case
+ * interpretation of the search text, used to order matches in camel-case.
+ */
+class SearchText {
+  final String text;
+  final String lowerCase;
+  final String camelCase;
+
+  SearchText(String searchText)
+      : text = searchText,
+        lowerCase = searchText.toLowerCase(),
+        camelCase = searchText.isEmpty() ? ''
+            : '${searchText.substring(0, 1).toUpperCase()}'
+              '${searchText.substring(1)}';
+
+  int get length() => text.length;
+
+  bool isEmpty() => length == 0;
+}
+
+/**
+ * [StringMatch] represents the case-insensitive matching of [searchText] as a
+ * substring within a [text]. The matched [text] is split into the [prefixText],

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

What variable does [text] refer to?

[Johnni Winther, 2012/08/23 10:19:50]

To the property, that is the getter 'text'.

+ * [infixText], and [suffixText], where [infixText] is the part matching the

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Why not just call it "matchText"? And perhaps "preMatchText"/"postMatchText".
Are they always needed, or could you just store the position of the match and
compute them dynamically if needed?

[Johnni Winther, 2012/08/23 10:19:50]

They are used extensively so I prefer creating them once.

+ * [searchText].
+ */
+class StringMatch {
+  final SearchText searchText;
+  final String prefixText;
+  final String infixText;
+  final String suffixText;
+
+  StringMatch(this.searchText,
+              this.prefixText, this.infixText, this.suffixText);
+
+  /**
+   * Returns the HTML representation of the match.
+   */
+  String toHtml() {
+    return '$prefixText'
+           '<span class="drop-down-link-highlight">$infixText</span>'
+           '$suffixText';
+  }
+
+  /**
+   * The text in which a substring matches [searchText].
+   */
+  String get text() =>
+      '$prefixText$infixText$suffixText';
+
+  /**
+   * Is `true` iff [searchText] matches the full [text] case-sensitively.

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Drop the quoting around 'true'. If you want something different, write it
[:true:].

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+   */
+  bool get isFullMatch() => text == searchText.text;
+
+  /**
+   * Is `true` iff [searchText] matches a substring of [text] case-sensitively.
+   */
+  bool get isExactMatch() => infixText == searchText.text;
+
+  /**
+   * Is `true` iff [searchText] matches a substring of [text] when [searchText]
+   * is interpreted as camel case.
+   */
+  bool get isCamelCaseMatch() => infixText == searchText.camelCase;
+}
+
+/**
+ * [Result] represents a match of the search text on a library, type or member.
+ */
+class Result {
+  final StringMatch prefix;
+  final StringMatch match;
+
+  final String library;
+  final String type;
+  final String args;
+  final String kind;
+  final String url;
+
+  TableRowElement row;
+
+  Result(this.match, this.kind, this.url,
+         [this.library, this.type, String args, this.prefix])
+      : this.args = args != null ? '<$args>' : '';
+
+  bool get isTopLevel() => prefix == null && type == null;
+
+  void addRow(TableElement table) {
+    if (row != null) return;
+
+    clickHandler(Event event) {
+      window.location.href = url;
+      hideDropDown();
+    }
+
+    row = table.insertRow(table.rows.length);
+    row.classes.add('drop-down-link-tr');
+    row.on.mouseDown.add((event) => hideDropDownSuspend = true);
+    row.on.click.add(clickHandler);
+    row.on.mouseUp.add((event) => hideDropDownSuspend = false);
+    var sb = new StringBuffer();
+    sb.add('<td class="drop-down-link-td">');
+    sb.add('<table class="drop-down-table"><tr><td colspan="2">');
+    if (kind == GETTER) {
+      sb.add('get ');
+    } else if (kind == SETTER) {
+      sb.add('set ');
+    }
+    sb.add(match.toHtml());
+    if (kind == CLASS || kind == INTERFACE || kind == TYPEDEF) {
+      sb.add(args);
+    } else if (kind == CONSTRUCTOR || kind == METHOD) {
+      sb.add('(...)');
+    }
+    sb.add('</td></tr><tr><td class="drop-down-link-kind">');
+    sb.add(kindToString(kind));
+    if (prefix != null) {
+      sb.add(' in ');
+      sb.add(prefix.toHtml());
+      sb.add(args);
+    } else if (type != null) {
+      sb.add(' in ');
+      sb.add(type);
+      sb.add(args);
+    }
+
+    sb.add('</td><td class="drop-down-link-library">');
+    if (library != null) {
+      sb.add('library $library');
+    }
+    sb.add('</td></tr></table></td>');
+    row.innerHTML = sb.toString();
+  }
+}
+
+/**
+ * Creates a [StringMatch] object for [text] if a substring matches
+ * [searchText], or returns [: null :] if no match is found.
+ */
+StringMatch obtainMatch(SearchText searchText, String text) {
+  if (searchText.isEmpty()) {
+    return new StringMatch(searchText, '', '', text);
+  }
+  int offset = text.toLowerCase().indexOf(searchText.lowerCase);
+  if (offset != -1) {
+    String prefixText = text.substring(0, offset);
+    String infixText = text.substring(offset, offset+searchText.length);

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Spaces around '+'. Ditto next line.

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+    String suffixText = text.substring(offset+searchText.length);
+    return new StringMatch(searchText, prefixText, infixText, suffixText);
+  }
+  return null;
+}
+
+int compareBools(bool a, bool b) {

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Document that it considers true bigger than false.
And that it doesn't handle null.

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+  if (a && !b) return -1;
+  else if (!a && b) return 1;
+  else return 0;
+}
+
+int compareInts(int a, int b) {
+  if (a < b) return -1;
+  else if (a > b) return 1;
+  else return 0;

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Aren't numbers comparable? I.e., a.compareTo(b)?

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+}
+
+int resultComparator(Result a, Result b) {

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

That's a lot of work to do in a sort comparison function.

[Johnni Winther, 2012/08/23 10:19:50]

Yes, but we have a lot of situations to handle!

+  // Favor top level entities.
+  int result = compareBools(a.isTopLevel, b.isTopLevel);
+  if (result != 0) return result;
+
+  if (a.prefix != null && b.prefix != null) {
+    // Favor full prefix matches.
+    result = compareBools(a.prefix.isFullMatch, b.prefix.isFullMatch);
+    if (result != 0) return result;
+  }
+
+  // Favor matches in the start.
+  result = compareBools(a.match.prefixText.isEmpty(),
+                        b.match.prefixText.isEmpty());
+  if (result != 0) return result;
+
+  // Favor exact case-sensitive matches.
+  result = compareBools(a.match.isExactMatch, b.match.isExactMatch);
+  if (result != 0) return result;
+
+  // Favor matches that do not break camel-case.
+  result = compareBools(a.match.isCamelCaseMatch, b.match.isCamelCaseMatch);
+  if (result != 0) return result;
+
+  // Favor matches close to the begining.
+  result = compareInts(a.match.prefixText.length,
+                       b.match.prefixText.length);
+  if (result != 0) return result;
+
+  if (a.type != null && b.type != null) {
+    // Favor short type names over long.
+    result = compareInts(a.type.length, b.type.length);
+    if (result != 0) return result;
+
+    // Sort type alphabetically.
+    result = a.type.toLowerCase().compareTo(b.type.toLowerCase());

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

This is particularly worrisome. You can have a quadratic number of comparisons
in a sort (worst case) and doing case conversion on both comparands seems likely
to explode.

Then again, we should probably have "String.compareNoCase" to handle that, and
we don't.

[Johnni Winther, 2012/08/23 10:19:50]

Yes, I looked for that!

+    if (result != 0) return result;
+  }
+
+  // Sort match alphabetically.
+  return a.match.text.toLowerCase().compareTo(b.match.text.toLowerCase());
+}
+
+List libraryList;
+InputElement searchInput;
+DivElement dropdown;

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Is this a global variable? That isn't even private?!?
Ick. 
Argh.
Ok, but still!!!

[Johnni Winther, 2012/08/23 10:19:50]

This is a web page and the DOM is global!

+
+/**
+ * Update the search drop down based on the current search text.
+ */
+updateDropDown(Event event) {
+  if (libraryList == null) return;
+  if (searchInput == null) return;
+  if (dropdown == null) return;
+
+  var results = <Result>[];
+  String text = searchInput.value;
+  if (text == currentSearchText) {
+    return;
+  }
+  if (text.isEmpty()) {
+    updateResults(text, results);
+    hideDropDown();
+    return;
+  }
+  if (text.contains('.')) {
+    // Search type members.
+    String typeText = text.substring(0, text.indexOf('.'));
+    String memberText = text.substring(text.indexOf('.') + 1);
+
+    if (typeText.isEmpty() && memberText.isEmpty()) {
+      // Don't search on '.'.
+    } else if (typeText.isEmpty()) {
+      // Search text is of the form '.id' => Look up members.
+      var searchText = new SearchText(memberText);
+      for (Map library in libraryList)  {
+        String libraryName = library[NAME];
+        if (library.containsKey(TYPES)) {
+          for (Map type in library[TYPES]) {
+            String typeName = type[NAME];
+            if (type.containsKey(MEMBERS)) {
+              for (Map member in type[MEMBERS]) {
+                StringMatch memberMatch = obtainMatch(searchText, member[NAME]);
+                if (memberMatch != null) {
+                  results.add(new Result(memberMatch, member[KIND],
+                      getTypeMemberUrl(libraryName, typeName, member),
+                      library: libraryName, type: typeName, args: type[ARGS]));
+                }
+              }
+            }
+          }
+        }
+      }
+    } else if (memberText.isEmpty()) {
+      // Search text is of the form 'Type.' => Look up members in 'Type'.
+      var searchText = new SearchText(typeText);
+      var emptyText = new SearchText(memberText);
+      for (Map library in libraryList)  {
+        String libraryName = library[NAME];
+        if (library.containsKey(TYPES)) {
+          for (Map type in library[TYPES]) {
+            String typeName = type[NAME];
+            StringMatch typeMatch = obtainMatch(searchText, typeName);
+            if (typeMatch != null) {
+              if (type.containsKey(MEMBERS)) {
+                for (Map member in type[MEMBERS]) {
+                  StringMatch memberMatch = obtainMatch(emptyText, member[NAME]);

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

Line too long.

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+                  results.add(new Result(memberMatch, member[KIND],
+                      getTypeMemberUrl(libraryName, typeName, member),
+                      library: libraryName, prefix: typeMatch));
+                }
+              }
+            }
+          }
+        }
+      }
+    } else {
+      // Search text is of the form 'Type.id' => Look up member 'id' in 'Type'.
+      var searchText = new SearchText(text);
+      var typeSearchText = new SearchText(typeText);
+      var memberSearchText = new SearchText(memberText);
+      for (Map library in libraryList)  {
+        String libraryName = library[NAME];
+        if (library.containsKey(TYPES)) {
+          for (Map type in library[TYPES]) {
+            String typeName = type[NAME];
+            StringMatch typeMatch = obtainMatch(typeSearchText, typeName);
+            if (typeMatch != null) {
+              if (type.containsKey(MEMBERS)) {
+                for (Map member in type[MEMBERS]) {
+                  StringMatch constructorMatch = obtainMatch(searchText,
+                                                             member[NAME]);
+                  if (constructorMatch != null) {
+                    results.add(new Result(constructorMatch, member[KIND],
+                        getTypeMemberUrl(libraryName, typeName, member),
+                        library: libraryName));
+                  } else {
+                    StringMatch memberMatch = obtainMatch(memberSearchText,
+                                                          member[NAME]);
+                    if (memberMatch != null) {
+                      results.add(new Result(memberMatch, member[KIND],
+                          getTypeMemberUrl(libraryName, typeName, member),
+                          library: libraryName, prefix: typeMatch,
+                          args: type[ARGS]));
+                    }
+                  }
+                }
+              }
+            }
+          }

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

These huge blobs of complex code would be great as separate functions.
Preferably with a meaningful name and good documentation.
I.e., I have no idea what happens here, and I can't read the code.

[Johnni Winther, 2012/08/23 10:19:50]

Refactored into several methods.

+        }
+      }
+    }
+  } else {
+    // Search all entities.
+    var searchText = new SearchText(text);
+    for (Map library in libraryList)  {
+      String libraryName = library[NAME];
+      StringMatch libraryMatch = obtainMatch(searchText, libraryName);
+      if (libraryMatch != null) {
+        results.add(new Result(libraryMatch, LIBRARY,
+                               getLibraryUrl(libraryName)));
+      }
+      if (library.containsKey(MEMBERS)) {
+        for (Map member in library[MEMBERS]) {
+          StringMatch memberMatch = obtainMatch(searchText, member[NAME]);
+          if (memberMatch != null) {
+            results.add(new Result(memberMatch, member[KIND],
+                                   getLibraryMemberUrl(libraryName, member),
+                                   library: libraryName));
+          }
+        }
+      }
+      if (library.containsKey(TYPES)) {
+        for (Map type in library[TYPES]) {
+          String typeName = type[NAME];
+          StringMatch typeMatch = obtainMatch(searchText, typeName);
+          if (typeMatch != null) {
+            results.add(new Result(typeMatch, type[KIND],
+                getTypeUrl(libraryName, type),
+                library: libraryName, args: type[ARGS]));
+          }
+          if (type.containsKey(MEMBERS)) {
+            for (Map member in type[MEMBERS]) {
+              StringMatch memberMatch = obtainMatch(searchText, member[NAME]);
+              if (memberMatch != null) {
+                results.add(new Result(memberMatch, member[KIND],
+                    getTypeMemberUrl(libraryName, typeName, member),
+                    library: libraryName, type: typeName, args: type[ARGS]));
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+  var elements = <Element>[];
+  var table = new TableElement();
+  table.classes.add('drop-down-table');
+  elements.add(table);
+
+  if (results.isEmpty()) {
+    var row = table.insertRow(0);
+    row.innerHTML = "<tr><td>No matches found for '$text'.</td></tr>";
+  } else {
+    results.sort(resultComparator);
+
+    var count = 0;
+    for (Result result in results) {
+      result.addRow(table);
+      if (++count >= 10) {
+        break;
+      }
+    }
+    if (results.length >= 10) {
+      var row = table.insertRow(table.rows.length);
+      row.innerHTML = '<tr><td>+ ${results.length-10} more.</td></tr>';
+      results = results.getRange(0, 10);
+    }
+  }
+  dropdown.elements = elements;
+  updateResults(text, results);
+  showDropDown();
+}
+
+String currentSearchText;
+Result _currentResult;
+List<Result> currentResults = const <Result>[];
+
+void updateResults(String searchText, List<Result> results) {
+  currentSearchText = searchText;
+  currentResults = results;
+  if (currentResults.isEmpty()) {
+    _currentResultIndex = -1;
+    currentResult = null;
+  } else {
+    _currentResultIndex = 0;
+    currentResult = currentResults[0];
+  }
+}
+
+int _currentResultIndex;
+
+void set currentResultIndex(int index) {
+  if (index < -1) {
+    return;
+  }
+  if (index >= currentResults.length) {
+    return;
+  }
+  if (index != _currentResultIndex) {
+    _currentResultIndex = index;
+    if (index >= 0) {
+      currentResult = currentResults[_currentResultIndex];
+    } else {
+      currentResult = null;
+    }
+  }
+}
+
+int get currentResultIndex() => _currentResultIndex;
+
+void set currentResult(Result result) {
+  if (_currentResult != result) {
+    if (_currentResult != null) {
+      _currentResult.row.classes.remove('drop-down-link-select');
+    }
+    _currentResult = result;
+    if (_currentResult != null) {
+      _currentResult.row.classes.add('drop-down-link-select');
+    }
+  }
+}
+
+Result get currentResult() => _currentResult;
+
+/**
+ * Navigate the search drop down using up/down inside the search field. Follow
+ * the result link on enter.
+ */
+void handleUpDown(KeyboardEvent event) {
+  if (event.keyIdentifier == KeyName.UP) {
+    currentResultIndex--;
+    event.preventDefault();
+  } else if (event.keyIdentifier == KeyName.DOWN) {
+    currentResultIndex++;
+    event.preventDefault();
+  } else if (event.keyIdentifier == KeyName.ENTER) {
+    if (currentResult != null) {
+      window.location.href = currentResult.url;
+      event.preventDefault();
+      hideDropDown();
+    }
+  }
+}
+
+/** Show the search drop down unless there are no current results. */
+void showDropDown() {
+  if (currentResults.isEmpty()) {
+    hideDropDown();
+  } else {
+    dropdown.style.visibility = 'visible';
+  }
+}
+
+/** Used to prevent hiding the drop down when it is clicked. */
+bool hideDropDownSuspend = false;
+
+/** Hide the search drop down unless suspended. */
+void hideDropDown() {
+  if (hideDropDownSuspend) return;
+
+  dropdown.style.visibility = 'hidden';
+}
+
+/** Activate search on Ctrl+F and F3. */
+void shortcutHandler(KeyboardEvent event) {
+  if (event.keyCode == 70/*F*/ && event.ctrlKey ||

[Lasse Reichstein Nielsen, 2012/08/20 13:07:58]

I prefer hex for keycodes. I.e., 0x46.

[Johnni Winther, 2012/08/23 10:19:50]

Done.

+      event.keyIdentifier == KeyName.F3) {
+    searchInput.focus();
+    event.preventDefault();
+  }
+}
+
+/** Setup search hooks. */
+void setupSearch(var libraries) {
+  libraryList = libraries;
+  searchInput = query('#q');
+  dropdown = query('#drop-down');
+
+  searchInput.on.keyDown.add(handleUpDown);
+  searchInput.on.keyUp.add(updateDropDown);
+  searchInput.on.change.add(updateDropDown);
+  searchInput.on.reset.add(updateDropDown);
+  searchInput.on.focus.add((event) => showDropDown());
+  searchInput.on.blur.add((event) => hideDropDown());
+  window.on.keyDown.add(shortcutHandler);
+}