Simple Trie for Domain Matching

trie.ts

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isValidDomain = false;
  hasWildcard = false;
}

class Trie {
  static build(allowedDomains: string | string[] | Trie, allowedSubDomains: string[]): Trie {
    if (allowedDomains instanceof Trie) return allowedDomains;
    if (!Array.isArray(allowedDomains)) allowedDomains = [allowedDomains];
    const trie = new Trie();
    for (const domain of allowedDomains) {
      const parsedDomain = safeURL(domain);
      if (!parsedDomain) throw new Error("allowedDomains has to be valid domain format");
      trie.insert(parsedDomain);
      for (const subdomain of allowedSubDomains) {
        const parsedSubDomain = safeURL(subdomain + "." + domain);
        if (!parsedSubDomain) throw new Error("allowedDomains has to be valid domain format");
        trie.insert(parsedSubDomain);
      }
    }
    return trie;
  }

  #root: TrieNode = new TrieNode();

  insert(domain: string): void {
    let node = this.#root;
    for (const part of domain.split(".").reverse()) {
      if (part === "*") {
        node.hasWildcard = true;
        break; // A wildcard applies to all subdomains, so stop here.
      }
      if (!node.children.has(part)) {
        node.children.set(part, new TrieNode());
      }
      node = node.children.get(part)!;
    }
    node.isValidDomain = true;
  }

  has(fqdn: string | null | undefined): boolean {
    const parsed = safeURL(fqdn);
    if (!parsed) return false;
    let node = this.#root;
    for (const part of parsed.split(".").reverse()) {
      if (node.hasWildcard) return true;
      if (!node.children.has(part)) return false;
      node = node.children.get(part)!;
    }
    return node.isValidDomain;
  }
}