Ticket #6465: parser.js

"use strict";

const NODE_YIELD = 1;
const NODE_MATCH_SYMBOL = 2;
const NODE_MATCH_STRING = 4;
const NODE_MATCH_STRING_TRAILING = NODE_MATCH_STRING | 1;
const NODE_MATCH_STRING_ANYWHERE = NODE_MATCH_STRING | 2;

const SYMBOL_END = 1;
const SYMBOL_DELIMITER = 2;
const SYMBOL_DOMAIN = 3;

let tree = [];

function getPrefixLength(s1, s2)
{
  let length = Math.min(s1.length, s2.length);
  for (let i = 0; i < length; i++)
  {
    if (s1[i] != s2[i])
      return i;
  }
  return length;
}

function injectNode(nodeType, nodeValue, nodes)
{
  for (let i = 0; i < nodes.length; i++)
  {
    let [thisNodeType, thisNodeValue, thisChildNodes] = nodes[i];
    if (nodeType == thisNodeType)
    {
      if (nodeValue == thisNodeValue)
        return thisChildNodes;

      if (nodeType & NODE_MATCH_STRING)
      {
        let prefixLength = getPrefixLength(nodeValue, thisNodeValue);
        if (prefixLength > 0)
        {
          if (prefixLength == thisNodeValue.length)
            return injectNode(NODE_MATCH_STRING_TRAILING,
                              nodeValue.slice(prefixLength),
                              thisChildNodes);

          let childNodes = [[NODE_MATCH_STRING_TRAILING,
                             thisNodeValue.slice(prefixLength),
                             thisChildNodes]];
          nodes[i] = [thisNodeType,
                      thisNodeValue.slice(0, prefixLength),
                      childNodes];

          if (prefixLength == nodeValue.length)
            return childNodes;

          let newChildNodes = [];
          childNodes.push([NODE_MATCH_STRING_TRAILING,
                           nodeValue.slice(prefixLength),
                           newChildNodes]);
          return newChildNodes;
        }
      }
    }
  }

  let childNodes = [];
  nodes.push([nodeType, nodeValue, childNodes]);
  return childNodes;
}

function parse(pattern, id)
{
  let offset = 0;
  let matchMode = NODE_MATCH_STRING_ANYWHERE;
  let nodes = tree;

  if (pattern.startsWith("|"))
  {
    offset++;
    matchMode = NODE_MATCH_STRING_TRAILING;

    if (pattern.startsWith("||"))
    {
      offset++;
      nodes = injectNode(NODE_MATCH_SYMBOL, SYMBOL_DOMAIN, nodes);
    }
  }

  while (true)
  {
    let asteriskIndex = pattern.indexOf("*", offset);
    let caretIndex = pattern.indexOf("^", offset);

    if (asteriskIndex != -1 && (caretIndex == -1 || asteriskIndex < caretIndex))
    {
      if (asteriskIndex > offset)
        nodes = injectNode(matchMode, pattern.slice(offset, asteriskIndex), nodes);

      matchMode = NODE_MATCH_STRING_ANYWHERE;
      offset = asteriskIndex + 1;

      continue;
    }

    if (caretIndex != -1 && (asteriskIndex == -1 || caretIndex < asteriskIndex))
    {
      if (caretIndex > offset ||
          nodes == tree && matchMode == NODE_MATCH_STRING_ANYWHERE)
        nodes = injectNode(matchMode, pattern.slice(offset, caretIndex), nodes);

      nodes = injectNode(NODE_MATCH_SYMBOL, SYMBOL_DELIMITER, nodes);
      matchMode = NODE_MATCH_STRING_TRAILING;
      offset = caretIndex + 1;

      continue;
    }

    break;
  }

  let impliedEnd = pattern.endsWith("|") && pattern.length > offset;
  let end = pattern.length - impliedEnd;

  if (end > offset)
  {
    nodes = injectNode(matchMode, pattern.slice(offset, end), nodes);
    matchMode = NODE_MATCH_STRING_TRAILING;
  }

  if (impliedEnd && matchMode == NODE_MATCH_STRING_TRAILING)
    nodes = injectNode(NODE_MATCH_SYMBOL, SYMBOL_END, nodes);

  nodes.push([NODE_YIELD, id, null]);
}

function match(s)
{
  let results = new Set();
  let queue = [[tree, 0]];

  while (queue.length > 0)
  {
    let [nodes, offset] = queue.shift();

    for (let [nodeType, nodeValue, childNodes] of nodes)
    {
      if (nodeType == NODE_YIELD)
      {
        results.add(nodeValue);
      }
      else if (nodeType == NODE_MATCH_STRING_TRAILING)
      {
        if (s.startsWith(nodeValue, offset))
          queue.push([childNodes, offset + nodeValue.length]);
      }
      else if (nodeType == NODE_MATCH_STRING_ANYWHERE)
      {
        let index = s.indexOf(nodeValue, offset);
        if (index != -1)
        {
          do
          {
            queue.push([childNodes, index + nodeValue.length]);
            index = s.indexOf(nodeValue, index + 1);
          }
          while (index != -1 && index < s.length)
        }
      }
      else if (nodeType == NODE_MATCH_SYMBOL)
      {
        if ((nodeValue == SYMBOL_END ||
             nodeValue == SYMBOL_DELIMITER) && offset >= s.length)
        {
          queue.push([childNodes, offset]);
        }
        else if (nodeValue == SYMBOL_DELIMITER)
        {
          let charCode = s.charCodeAt(offset);
          if (charCode <= 0x24 ||
              charCode >= 0x26 && charCode <= 0x2c ||
              charCode == 0x2f ||
              charCode >= 0x3a && charCode <= 0x40 ||
              charCode >= 0x5b && charCode <= 0x5e ||
              charCode == 0x60 ||
              charCode >= 0x7b && charCode <= 0x7f)
            queue.push([childNodes, offset + 1]);
        }
        else if (nodeValue == SYMBOL_DOMAIN)
        {
          let index = s.indexOf(":");
          if (index >= offset)
          {
            while (s.startsWith("/", ++index))
              ;

            while (true)
            {
              queue.push([childNodes, index]);

              let dotIndex = s.indexOf(".", index);
              if (dotIndex == -1 || s.lastIndexOf("/", index) >= dotIndex)
                break;

              index = dotIndex + 1;
            }
          }
        }
      }
    }
  }

  return results;
}

var readline = require("readline");
var performance = require("perf_hooks").performance;
var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
  terminal: false
});

let counter = 0;
//let filters = {};
rl.on("line", line => {
  line = line.trim();
  if (line != "" && !line.startsWith("!") && !line.startsWith("["))
  {
    let optIndex = line.indexOf("$");
    if (optIndex != -1)
      line = line.slice(0, optIndex);
    if (!line.startsWith("/") || !line.endsWith("/")) {
      parse(line, ++counter);
//      filters[counter] = line;
    }
  }
});

performance.mark("C");
rl.on("close", () => {
  performance.mark("D");
  performance.mark("B");
  performance.measure("Y", "C", "D");
  console.log(performance.getEntriesByName("Y")[0].duration);
  console.log(process.memoryUsage());
//  console.log(JSON.stringify(tree, null, 2));
//  console.log(filters);
  performance.mark("A");
  match("http://www.example.com/adbanner");
  performance.mark("B");
  performance.measure("X", "A", "B");
  console.log(performance.getEntriesByName("X")[0].duration);
});