Skip to content

A fully open source & end-to-end encrypted note taking alternative to Evernote.

14.0 KB
Raw Blame
/*
This file is part of the Notesnook project (https://notesnook.com/)

Copyright (C) 2023 Streetwriters (Private) Limited

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

import dayjs from "dayjs";
import { servicesVersion } from "typescript";

type ASTNode = QueryNode | PhraseNode | OperatorNode | FieldPhraseNode;

type QueryNode = {
  type: "query";
  children: ASTNode[];
};

type PhraseNode = {
  type: "phrase";
  value: string[];
};

type FieldPhraseNode = {
  type: "field_phrase";
  field: string;
  value: QueryNode;
};

type FieldToken = {
  field?: string;
  fieldOccurrence?: number;
  token: string;
};

type OperatorNode = {
  type: "AND" | "OR" | "NOT";
};

const SUPPORTED_FIELDS = {
  title: (ast) => {
    const node =
      ast.find((a) => a.type === "field_phrase" && a.field === "title") ||
      ast.find((a) => a.type === "query");
    return node && serializeQuery(node);
  },
  content: (ast) => {
    const node =
      ast.find((a) => a.type === "field_phrase" && a.field === "content") ||
      ast.find((a) => a.type === "query");
    return node && serializeQuery(node);
  },

  // array
  tag: (ast) => parseArrayField("tag", ast),
  color: (ast) => parseArrayField("color", ast),

  // date
  edited_before: (ast) => parseDateField("edited_before", ast),
  edited_after: (ast) => parseDateField("edited_after", ast),
  created_before: (ast) => parseDateField("created_before", ast),
  created_after: (ast) => parseDateField("created_after", ast),

  // boolean
  pinned: (ast) => parseBooleanField("pinned", ast),
  locked: (ast) => parseBooleanField("locked", ast),
  readonly: (ast) => parseBooleanField("readonly", ast),
  favorite: (ast) => parseBooleanField("favorite", ast),
  archived: (ast) => parseBooleanField("archived", ast),
  tagged: (ast) => parseBooleanField("tagged", ast),
  colored: (ast) => parseBooleanField("colored", ast),
  in_notebook: (ast) => parseBooleanField("in_notebook", ast)
} satisfies Record<string, (ast: (QueryNode | FieldPhraseNode)[]) => unknown>;

const ARRAY_FIELDS = ["tag", "color"];

function isFieldSupported(field: string) {
  return field in SUPPORTED_FIELDS;
}

function parseBooleanField(
  field: string,
  ast: (QueryNode | FieldPhraseNode)[]
): boolean | null {
  const node = ast.find(
    (a): a is FieldPhraseNode => a.type === "field_phrase" && a.field === field
  );
  const sql = node ? generateSQL(node.value) : "";
  return sql === "false" ? false : sql === "true" ? true : null;
}

function parseArrayField(
  field: string,
  ast: (QueryNode | FieldPhraseNode)[]
): string[] | null {
  const values = ast
    .filter(
      (a): a is FieldPhraseNode =>
        a.type === "field_phrase" && a.field === field
    )
    .map((a) => unquoteExactValue(generateSQL(a.value)));
  return values.length > 0 ? values : null;
}

function unquoteExactValue(value: string) {
  if (!value.startsWith('"') || !value.endsWith('"')) return value;
  return value.slice(1, -1).replace(/""/g, '"');
}

function parseDateField(
  field: string,
  ast: (QueryNode | FieldPhraseNode)[]
): number | null {
  const node = ast.find(
    (a): a is FieldPhraseNode => a.type === "field_phrase" && a.field === field
  );
  const date = node ? dayjs(generateSQL(node.value)) : null;
  return date?.isValid() ? date.toDate().getTime() : null;
}

const INVALID_QUERY_REGEX = /[!"#$%&'()*+,\-./:;<>=?@[\\\]^_`{|}~§]/;
function escapeSQLString(str: string): string {
  if (str.startsWith('"') && str.endsWith('"')) {
    const innerStr = str.slice(1, -1).replace(/"/g, '""');
    return `"${innerStr}"`;
  }

  const hasInvalidSymbol = INVALID_QUERY_REGEX.test(str);
  const isWildcard =
    str.startsWith("*") ||
    str.endsWith("*") ||
    str.startsWith("%") ||
    str.endsWith("%");
  if (hasInvalidSymbol || isWildcard) {
    return `"${str.replace(/"/g, '""')}"`;
  }

  // if (isWildcard) {
  //   return str.replace(/(.+?)(\*?$)/gm, (_, text, end) => {
  //     return `${escapeSQLString(text)}${end}`;
  //   });
  // }

  // if (str.includes("-")) {
  //   return `"${str.replace(/"/g, '""')}"`;
  // }

  return str.replace(/"/g, '""');
}

function tokenizeWithFields(query: string): FieldToken[] {
  const tokens: FieldToken[] = [];
  let buffer = "";
  let isQuoted = false;
  let currentField: string | undefined = undefined;
  let fieldOccurrence = 0;

  const pushToken = () => {
    if (buffer.length > 0) {
      tokens.push({
        field: currentField,
        fieldOccurrence: currentField ? fieldOccurrence : undefined,
        token: buffer
      });
      buffer = "";
    }
  };

  for (let i = 0; i < query.length; ++i) {
    const char = query[i];
    if (char === '"') {
      isQuoted = !isQuoted;
    }
    if (char === " " && !isQuoted) {
      pushToken();
    } else if (char === ":" && !isQuoted) {
      // Check for field
      const maybeField = buffer.trim().toLowerCase();
      if (isFieldSupported(maybeField)) {
        currentField = maybeField;
        fieldOccurrence++;
        buffer = "";
      } else {
        buffer += char;
      }
    } else {
      buffer += char;
    }
  }
  pushToken();

  return tokens;
}

// Helper: group tokens by field
function groupTokensByField(tokens: FieldToken[]) {
  const groups: Array<{ field?: string; tokens: string[] }> = [];
  let currentField: string | undefined = undefined;
  let currentOccurrence: number | undefined = undefined;
  let currentTokens: string[] = [];

  for (const { field, fieldOccurrence, token } of tokens) {
    const isArrayField = ARRAY_FIELDS.includes(field || "");
    const shouldStartNewGroup =
      field !== currentField ||
      (isArrayField && fieldOccurrence !== currentOccurrence);

    if (shouldStartNewGroup) {
      if (currentTokens.length > 0) {
        groups.push({ field: currentField, tokens: currentTokens });
        currentTokens = [];
      }
      currentField = field;
      currentOccurrence = fieldOccurrence;
    }
    currentTokens.push(token);
  }
  if (currentTokens.length > 0) {
    groups.push({ field: currentField, tokens: currentTokens });
  }
  return groups;
}

// Parse a group of tokens into a QueryNode (handles boolean ops, etc)
function parseTokensToQueryNode(tokens: string[]): QueryNode {
  const ast: QueryNode = { type: "query", children: [] };
  let currentPhrase: string[] = [];

  for (const token of tokens) {
    if (token === "AND" || token === "OR" || token === "NOT") {
      if (currentPhrase.length > 0) {
        ast.children.push({ type: "phrase", value: currentPhrase });
        currentPhrase = [];
      }
      ast.children.push({ type: token });
    } else {
      currentPhrase.push(token);
    }
  }
  if (currentPhrase.length > 0) {
    ast.children.push({ type: "phrase", value: currentPhrase });
  }
  return ast;
}

function transformQueryNode(ast: QueryNode): QueryNode {
  const transformedAST: QueryNode = { ...ast, children: [] };
  let lastWasPhrase = false;

  for (let i = 0; i < ast.children.length; i++) {
    const child = ast.children[i];

    if (child.type === "phrase") {
      if (lastWasPhrase) {
        transformedAST.children.push({ type: "AND" });
      }
      const transformedPhrase = child.value.map(escapeSQLString);
      transformedAST.children.push({
        type: "phrase",
        value: transformedPhrase
      });
      lastWasPhrase = true;
    } else if (
      child.type === "AND" ||
      child.type === "OR" ||
      child.type === "NOT"
    ) {
      if (
        lastWasPhrase &&
        i + 1 < ast.children.length &&
        ast.children[i + 1].type === "phrase"
      ) {
        transformedAST.children.push(child);
        lastWasPhrase = false;
      }
    }
  }

  return transformedAST;
}

function generateSQL(ast: QueryNode): string {
  return ast.children
    .map((child) => {
      if (child.type === "phrase") {
        return child.value.filter((v) => v.length >= 3).join(" AND ");
      }
      if (child.type === "AND" || child.type === "OR" || child.type === "NOT") {
        return child.type;
      }
      return "";
    })
    .join(" ");
}

export type QueryTerm = { type: "term"; value: string };
export type QueryExpression =
  | QueryTerm
  | {
      type: OperatorNode["type"];
      left: QueryExpression;
      right: QueryExpression;
    };

// same as FTS5: NOT binds tighter than AND which binds tighter than OR
const PRECEDENCE: Record<OperatorNode["type"], number> = {
  OR: 1,
  AND: 2,
  NOT: 3
};

/**
 * Terms shorter than 3 characters cannot be matched as substrings
 * by the trigram tokenizer.
 */
function isShortTerm(term: QueryTerm) {
  return term.value.length < 3;
}

export function hasShortTerms(expression: QueryExpression): boolean {
  if (expression.type === "term") return isShortTerm(expression);
  return hasShortTerms(expression.left) || hasShortTerms(expression.right);
}

export function serializeExpression(expression: QueryExpression): string {
  if (expression.type === "term") return expression.value;

  const precedence = PRECEDENCE[expression.type];
  const serialize = (child: QueryExpression, needsParens: boolean) =>
    needsParens
      ? `(${serializeExpression(child)})`
      : serializeExpression(child);
  const left = serialize(
    expression.left,
    expression.left.type !== "term" &&
      PRECEDENCE[expression.left.type] < precedence
  );
  // operators are left associative so the right operand
  // needs parentheses even if it has the same precedence
  const right = serialize(
    expression.right,
    expression.right.type !== "term" &&
      PRECEDENCE[expression.right.type] <= precedence
  );
  return `${left} ${expression.type} ${right}`;
}

function buildExpression(ast: QueryNode): QueryExpression | undefined {
  // words in a phrase are ANDed together
  const items: (QueryTerm | undefined | OperatorNode["type"])[] = [];
  for (const child of ast.children) {
    if (child.type === "phrase") {
      child.value.forEach((value, index) => {
        if (index > 0) items.push("AND");
        // an empty phrase ("") cannot match anything so we drop it
        items.push(value === '""' ? undefined : { type: "term", value });
      });
    } else if (
      child.type === "AND" ||
      child.type === "OR" ||
      child.type === "NOT"
    ) {
      items.push(child.type);
    }
  }
  if (items.length === 0) return;

  // items alternate between terms & operators (guaranteed by
  // transformQueryNode) so we can use simple precedence climbing.
  let index = 0;
  const parse = (minPrecedence: number): QueryExpression | undefined => {
    let left: QueryExpression | undefined = items[index++] as
      | QueryTerm
      | undefined;
    while (index < items.length) {
      const operator = items[index] as OperatorNode["type"];
      const precedence = PRECEDENCE[operator];
      if (precedence < minPrecedence) break;
      index++;
      left = combine(operator, left, parse(precedence + 1));
    }
    return left;
  };
  return parse(1);
}

function combine(
  operator: OperatorNode["type"],
  left: QueryExpression | undefined,
  right: QueryExpression | undefined
): QueryExpression | undefined {
  if (!left) return operator === "NOT" ? undefined : right;
  if (!right) return left;
  return { type: operator, left, right };
}

// Main transformer: returns (QueryNode | FieldPhraseNode)[]
export function transformQuery(query: string): {
  [K in keyof typeof SUPPORTED_FIELDS]?: ReturnType<
    (typeof SUPPORTED_FIELDS)[K]
  >;
} & { filters: number } {
  const tokens = tokenizeWithFields(query);
  const groups = groupTokensByField(tokens);

  const ast = groups.map((group) => {
    const node = parseTokensToQueryNode(group.tokens);
    const transformedNode = transformQueryNode(node);
    if (group.field) {
      return {
        type: "field_phrase",
        field: group.field,
        value: transformedNode
      } as FieldPhraseNode;
    } else {
      return transformedNode;
    }
  });

  let filters = 0;
  const fields = Object.fromEntries(
    Object.entries(SUPPORTED_FIELDS).map(([key, field]) => {
      const value = field(ast);
      if (
        value !== null &&
        value !== undefined &&
        !["content", "title"].includes(key)
      )
        filters++;
      return [key, value];
    })
  );
  return { ...fields, filters };
}

function serializeQuery(node: QueryNode | FieldPhraseNode) {
  const ast = node.type === "query" ? node : node.value;
  const expression = buildExpression(ast);
  return {
    query: expression ? serializeExpression(expression) : "",
    expression,
    tokens: tokenizeAst(ast)
  };
}

export interface QueryTokens {
  andTokens: string[];
  orTokens: string[];
  notTokens: string[];
}

function tokenizeAst(ast: QueryNode): QueryTokens {
  const result: QueryTokens = {
    andTokens: [],
    orTokens: [],
    notTokens: []
  };

  let isNextNot = false;
  let isNextOr = false;

  for (let i = 0; i < ast.children.length; i++) {
    const node = ast.children[i];

    if (node.type === "NOT") {
      isNextNot = true;
      continue;
    }

    if (node.type === "OR") {
      isNextOr = true;
      continue;
    }

    if (node.type === "phrase") {
      // Handle each word in the phrase
      for (const word of node.value) {
        if (
          result.orTokens.includes(word) ||
          result.andTokens.includes(word) ||
          result.notTokens.includes(word)
        ) {
          isNextOr = false;
          isNextNot = false;
          continue;
        }
        if (isNextOr) {
          result.orTokens.push(word);
        } else if (isNextNot) {
          result.notTokens.push(word);
        } else {
          result.andTokens.push(word);
        }
      }

      isNextOr = false;
      isNextNot = false;
    }
  }

  return result;
}