Repository: DestinyItemManager/DIM
Pull request #5498 (2020-07-24 06:18:23)

Integrate the new query parser
This integrates our new query parser into the existing filter system. I tried to leave things as close to the same place they were as possible to not interfere with the filter table refactor.

I haven't measured it, but it *feels* like the filter function generated by this is faster. I could optimize it further but it seems to do OK.

TODO:

* [x] Some filters don't appear to work
* [x] Parse errors bubble out and crash the page
* [x] Unnecessary optimizations


Patch:
diff --git a/docs/CHANGELOG.md b/docs/CHANGELOG.md
index b4244ab85..56d9f3c28 100644
--- a/docs/CHANGELOG.md
+++ b/docs/CHANGELOG.md
@@ -1,5 +1,7 @@
 ## Next
 
+* Searches now support parentheses for grouping, the "and" keyword, and the "not" keyword. Example: `(is:weapon and is:sniperrifle) or not (is:armor and modslot:arrival)`. "and" has higher precedence than "or", which has higher precedence than just a space (which still means "and").
+
 ## 6.22.1 <span className="changelog-date">(2020-07-27)</span>
 
 ## 6.22.0 <span className="changelog-date">(2020-07-26)</span>
diff --git a/src/app/search/query-parser.ts b/src/app/search/query-parser.ts
index b30ff4c3f..8a3f363f6 100644
--- a/src/app/search/query-parser.ts
+++ b/src/app/search/query-parser.ts
@@ -26,30 +26,30 @@ import _ from 'lodash';
  * A tree of the parsed query. Boolean/unary operators have children (operands)that
  * describe their relationship.
  */
-type QueryAST = (AndOp | OrOp | NotOp | FilterOp | NoOp) & {
+export type QueryAST = (AndOp | OrOp | NotOp | FilterOp | NoOp) & {
   error?: Error;
 };
 
 /** If ALL of of the operands are true, this resolves to true. There may be any number of operands. */
-interface AndOp {
+export interface AndOp {
   op: 'and';
   operands: QueryAST[];
 }
 
 /** If any of the operands is true, this resolves to true. There may be any number of operands. */
-interface OrOp {
+export interface OrOp {
   op: 'or';
   operands: QueryAST[];
 }
 
 /** An operator which negates the result of its only operand. */
-interface NotOp {
+export interface NotOp {
   op: 'not';
   operand: QueryAST;
 }
 
 /** This represents one of our filter function definitions, such as is:, season:, etc. */
-interface FilterOp {
+export interface FilterOp {
   op: 'filter';
   /**
    * The name of the filter function, without any trailing :. The only weird case is
@@ -231,7 +231,11 @@ export function parseQuery(query: string): QueryAST {
   }
 
   const tokens = new PeekableGenerator(lexer(query));
-  if (!tokens.peek()) {
+  try {
+    if (!tokens.peek()) {
+      return { op: 'noop' };
+    }
+  } catch (e) {
     return { op: 'noop' };
   }
   const ast = parse(tokens);
@@ -273,8 +277,8 @@ const negation = /-\s*/y;
 // `not`, `or`, and `and` keywords. or and not can be preceded by whitespace, and any of them can be followed by whitespace.
 // `not` can't be preceded by whitespace because that whitespace is an implicit `and`.
 const booleanKeywords = /(not|\s+or|\s+and)\s+/y;
-// Filter names like is:, stat:discipline:, etc
-const filterName = /[a-z]+:([a-z]+:)?/y;
+// Filter names like is:, stat:, etc
+const filterName = /[a-z]+:/y;
 // Arguments to filters are pretty unconstrained
 const filterArgs = /[^\s()]+/y;
 // Words without quotes are basically any non-whitespace that doesn't terminate a group
diff --git a/src/app/search/search-filter.ts b/src/app/search/search-filter.ts
index cf935645c..178ab52d3 100644
--- a/src/app/search/search-filter.ts
+++ b/src/app/search/search-filter.ts
@@ -52,6 +52,7 @@ import { settingsSelector } from 'app/settings/reducer';
 import store from '../store/store';
 import { getStore } from 'app/inventory/stores-helpers';
 import { DestinyVersion } from '@destinyitemmanager/dim-api-types';
+import { parseQuery, QueryAST } from './query-parser';
 
 /**
  * (to the tune of TMNT) ♪ string processing helper functions ♫
@@ -74,21 +75,9 @@ const startWordRegexp = memoizeOne(
     new RegExp(`${isLatinBased() ? '\\b' : ''}${escapeRegExp(s)}`, 'i')
 );
 
-// String.match results like [
-// "-not:tagged", (0: discarded)
-// "-",           (1: invertString)
-// "not:",        (2: discarded)
-// "not",         (3: filterName)
-// "tagged"       (4: filterValue)
-// ]
-const searchTermRegex = /^(-?)(([^:]+):)?(.+)$/;
-
 /** returns input string toLower, and stripped of accents if it's a latin language */
 const plainString = (s: string): string => (isLatinBased() ? latinise(s) : s).toLowerCase();
 
-/** remove starting and ending quotes ('") e.g. for notes:"this string" */
-const trimQuotes = (s: string) => s.replace(/(^['"]|['"]$)/g, '');
-
 /** strings representing math checks */
 const operators = ['<', '>', '<=', '>=', '='];
 const operatorsInLengthOrder = _.sortBy(operators, (s) => -s.length);
@@ -585,142 +574,98 @@ function searchFilters(
         return (item: DimItem) => getTag(item, itemInfos) !== 'archive';
       }
 
-      // http://blog.tatedavies.com/2012/08/28/replace-microsoft-chars-in-javascript/
-      query = query.replace(/[\u2018|\u2019|\u201A]/g, "'");
-      query = query.replace(/[\u201C|\u201D|\u201E]/g, '"');
-      // \S*?(["']).*?\1 -> match `is:"stuff here"` or `is:'stuff here'`
-      // [^\s"']+ -> match is:stuff
-      const searchTerms = query.match(/\S*?(["']).*?\1|[^\s"']+/g) || [];
-      interface Filter {
-        invert: boolean;
-        filterValue: string;
-        filterName: string;
-        orFilters?: Filter[];
-      }
-      const filterStack: Filter[] = [];
-
-      // The entire implementation of "or" is a dirty hack - we should really
-      // build an expression tree instead. But here, we flip a flag when we see
-      // an "or" token, and then on the next filter we instead combine the filter
-      // with the previous one in a hacked-up "or" node that we'll handle specially.
-      let or = false;
-
-      function addFilterToStack(filterName: string, filterValue: string, invert: boolean) {
-        const filterDef: Filter = { filterName, filterValue, invert };
-        if (or && filterStack.length) {
-          const lastFilter = filterStack.pop();
-          filterStack.push({
-            filterName: 'or',
-            invert: false,
-            filterValue: '',
-            orFilters: [...(lastFilter!.orFilters! || [lastFilter]), filterDef],
-          });
-        } else {
-          filterStack.push(filterDef);
-        }
-        or = false;
-      }
-
-      for (const search of searchTerms) {
-        const [, invertString, , filterName, filterValue] = search.match(searchTermRegex) || [];
-        let invert = Boolean(invertString);
-
-        if (filterValue === 'or') {
-          or = true;
-        } else {
-          switch (filterName) {
-            case 'not':
-              invert = !invert;
-            // fall through intentionally after setting "not" inversion
-            case 'is': {
-              // do a lookup by filterValue (i.e. arc)
-              // to find the appropriate filterFunction (i.e. dmg)
-              const filterFunction = searchConfig.keywordToFilter[filterValue];
-              if (filterFunction) {
-                addFilterToStack(filterFunction, filterValue, invert);
+      const parsedQuery = parseQuery(query);
+      const filterTable = this.filters;
+
+      // Transform our query syntax tree into a filter function by recursion.
+      // TODO: break these out into standalone, tested functions!
+      const transformAST = (ast: QueryAST): ((item: DimItem) => boolean) => {
+        switch (ast.op) {
+          case 'and': {
+            const fns = ast.operands.map(transformAST);
+            return (item) => {
+              for (const fn of fns) {
+                if (!fn(item)) {
+                  return false;
+                }
               }
-              break;
-            }
-            // filters whose filterValue needs outer quotes trimmed
-            case 'notes':
-            case 'perk':
-            case 'perkname':
-            case 'name':
-            case 'description':
-            case 'wishlistnotes':
-              addFilterToStack(filterName, trimQuotes(filterValue), invert);
-              break;
-            // normalize synonyms
-            case 'light':
-            case 'power':
-              addFilterToStack('light', filterValue, invert);
-              break;
-            case 'quality':
-            case 'percentage':
-              addFilterToStack('quality', filterValue, invert);
-              break;
-            // mutate filterValues where keywords (forge) should be translated into seasons (5)
-            case 'powerlimitseason':
-            case 'sunsetsafter':
-              addFilterToStack('sunsetsafter', replaceSeasonTagWithNumber(filterValue), invert);
-              break;
-            case 'season':
-              addFilterToStack('season', replaceSeasonTagWithNumber(filterValue), invert);
-              break;
-            // pass these filter names and values unaltered
-            case 'masterwork':
-            case 'powerlimit':
-            case 'year':
-            case 'stack':
-            case 'count':
-            case 'energycapacity':
-            case 'breaker':
-            case 'maxbasestatvalue':
-            case 'maxstatloadout':
-            case 'maxstatvalue':
-            case 'tag':
-            case 'level':
-            case 'rating':
-            case 'ratingcount':
-            case 'id':
-            case 'hash':
-            case 'source':
-            case 'modslot':
-            case 'holdsmod':
-              addFilterToStack(filterName, filterValue, invert);
-              break;
-            // stat filter has sub-searchterm and needs further separation
-            case 'basestat':
-            case 'stat': {
-              const [statName, statValue, shouldntExist] = filterValue.split(':');
-              const statFilterName = filterName === 'basestat' ? `base${statName}` : statName;
-              if (!shouldntExist) {
-                addFilterToStack(statFilterName, statValue, invert);
+              return true;
+            };
+          }
+          case 'or': {
+            const fns = ast.operands.map(transformAST);
+            return (item) => {
+              for (const fn of fns) {
+                if (fn(item)) {
+                  return true;
+                }
               }
-              break;
-            }
-            // if nothing else matches we cast a wide net and do the powerful keyword search
-            default:
-              if (!/^\s*$/.test(filterValue)) {
-                addFilterToStack('keyword', trimQuotes(filterValue), invert);
+              return false;
+            };
+          }
+          case 'not': {
+            const fn = transformAST(ast.operand);
+            return (item) => !fn(item);
+          }
+          case 'filter': {
+            // TODO: break this out into its own function that takes the filter table as an arg
+            const { type: filterName, args: filterValue } = ast;
+
+            // Generate a filter function from the filters table
+            const filterByTable = (filterName: string, filterValue: string) => {
+              if (filterTable[filterName]) {
+                const filterFunction = filterTable[filterName] as (
+                  item: DimItem,
+                  val: string
+                ) => boolean;
+                return (item: DimItem) => filterFunction.call(filterTable, item, filterValue);
+              }
+              return () => true;
+            };
+
+            switch (filterName) {
+              case 'is': {
+                // do a lookup by filterValue (i.e. arc)
+                // to find the appropriate filterFunction (i.e. dmg)
+                const filterName = searchConfig.keywordToFilter[filterValue];
+                return filterByTable(filterName, filterValue);
+              }
+              // normalize synonyms
+              case 'light':
+              case 'power':
+                return filterByTable('light', filterValue);
+              case 'quality':
+              case 'percentage':
+                return filterByTable('quality', filterValue);
+              // mutate filterValues where keywords (forge) should be translated into seasons (5)
+              case 'powerlimitseason':
+              case 'sunsetsafter':
+                return filterByTable('sunsetsafter', replaceSeasonTagWithNumber(filterValue));
+              case 'season':
+                return filterByTable('season', replaceSeasonTagWithNumber(filterValue));
+              // stat filter has sub-searchterm and needs further separation
+              case 'basestat':
+              case 'stat': {
+                const [statName, statValue, shouldntExist] = filterValue.split(':');
+                const statFilterName = filterName === 'basestat' ? `base${statName}` : statName;
+                if (!shouldntExist) {
+                  return filterByTable(statFilterName, statValue);
+                }
+                break;
               }
+              default:
+                // All other keywords just pass through to filter table lookups
+                return filterByTable(filterName, filterValue);
+            }
+
+            return () => true;
           }
         }
-      }
 
-      return (item: DimItem) =>
-        filterStack.every((filter) => {
-          let result;
-          if (filter.orFilters) {
-            result = filter.orFilters.some((filter) => {
-              const result = this.filters[filter.filterName]?.(item, filter.filterValue);
-              return filter.invert ? !result : result;
-            });
-          } else {
-            result = this.filters[filter.filterName]?.(item, filter.filterValue);
-          }
-          return filter.invert ? !result : result;
-        });
+        return () => true;
+      };
+
+      return transformAST(parsedQuery);
     }),
 
     /**


Test patch:
diff --git a/src/app/search/__snapshots__/query-parser.test.ts.snap b/src/app/search/__snapshots__/query-parser.test.ts.snap
index d727a0afc..746ea3ac1 100644
--- a/src/app/search/__snapshots__/query-parser.test.ts.snap
+++ b/src/app/search/__snapshots__/query-parser.test.ts.snap
@@ -542,9 +542,9 @@ Object {
       },
     },
     Object {
-      "args": "<55",
+      "args": "total:<55",
       "op": "filter",
-      "type": "stat:total",
+      "type": "stat",
     },
   ],
 }
@@ -598,8 +598,8 @@ Array [
   ],
   Array [
     "filter",
-    "stat:total",
-    "<55",
+    "stat",
+    "total:<55",
   ],
 ]
 `;