How many well-formed JSON strings are there?

jsoncount.js

/**
  Code for enumerating valid JSON strings.
  Bounds checking is the responsibility of the caller.
  This code attempts to be somewhat readable without significantly impacting performance.
  https://qntm.org/jsoncount
  https://qntm.org/jsonutf8
*/

import assert from 'node:assert/strict'

// First some constants
const NUM_DIGITS = BigInt(['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'].length)
const NUM_1_BYTE_CODE_POINTS = (0x007Fn + 1n) - 0x0020n - BigInt(['\\', '"'].length) // 94
const NUM_2_BYTE_CODE_POINTS = (0x07FFn + 1n) - 0x0080n // 1920
const NUM_SURROGATE_CODE_POINTS = (0xDFFFn + 1n) - 0xD800n // 2048
const NUM_3_BYTE_CODE_POINTS = (0xFFFFn + 1n) - 0x0800n - NUM_SURROGATE_CODE_POINTS // 61440
const NUM_4_BYTE_CODE_POINTS = (0x10FFFFn + 1n) - 0x10000n // 1048576
const NUM_ESCAPES = BigInt(['"', '\\', '/', 'b', 'f', 'n', 'r', 't'].length) // 8
const NUM_HEX_CODE_POINTS = BigInt([
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  'A', 'B', 'C', 'D', 'E', 'F',
  'a', 'b', 'c', 'd', 'e', 'f'
].length) // 22, not 16
const NUM_HEX_ESCAPES = NUM_HEX_CODE_POINTS ** 4n // 234,256, not 65,536
const NUM_ES = BigInt(['E', 'e'].length) // 2
const NUM_SIGNS = BigInt(['-', '+'].length) // 2

// Memoization is incredibly important as the numbers get larger,
// there are many combinations
const memoize = f => {
  const known = []
  return n => known[n] ??= f(n)
}

// Now for some enumeration.
// Use BigInts throughout because we're going to be exceeding `Number.MAX_SAFE_INTEGER` at N = 5

export class Counter {
  #numWs
  #encoding

  constructor (allowWs, encoding) {
    this.#numWs = allowWs
      ? BigInt(['\u0020', '\u000A', '\u000D', '\u0009'].length) // 4
      : 0n
    this.#encoding = encoding
  }

  // E.g. "123"
  // [1-9][0-9]*
  countPositiveIntegers (n) {
    return (NUM_DIGITS - 1n) * NUM_DIGITS ** BigInt(n - 1)
  }

  // E.g. "123.456"
  // 0.[0-9]{3}
  // [1-9][0-9].[0-9][0-9], [1-9][0-9][0-9].[0-9]
  countDecimals (n) {
    return NUM_DIGITS ** BigInt(n - 2) +
    (NUM_DIGITS - 1n) * NUM_DIGITS ** BigInt(n - 2) * BigInt(n - 2)
  }

  // E.g. "123e456"
  // 0[eE][0-9][0-9][0-9]
  // [1-9][eE][0-9][0-9][0-9], [1-9][0-9][eE][0-9][0-9], [1-9][0-9][0-9][eE][0-9]
  countExponents (n) {
    return NUM_ES * NUM_DIGITS ** BigInt(n - 2) +
    (NUM_DIGITS - 1n) * NUM_ES * NUM_DIGITS ** BigInt(n - 2) * BigInt(n - 2)
  }

  // E.g. "123e+456"
  // 0[eE][+-][0-9][0-9][0-9]
  // [1-9][eE][+-][0-9][0-9][0-9], [1-9][0-9][eE][+-][0-9][0-9], [1-9][0-9][0-9][eE][+-][0-9]
  countSignedExponents (n) {
    return NUM_ES * NUM_SIGNS * NUM_DIGITS ** BigInt(n - 3) +
    (NUM_DIGITS - 1n) * NUM_ES * NUM_SIGNS * NUM_DIGITS ** BigInt(n - 3) * BigInt(n - 3)
  }

  // E.g. "123.456e789"
  // 0.[0-9][eE][0-9], 1 combination
  // [1-9].[0-9][eE][0-9], 1 combination
  // 0.[0-9][eE][0-9][0-9], 0.[0-9][0-9][eE][0-9], 2 combinations
  // [1-9].[0-9][eE][0-9][0-9], [1-9].[0-9][0-9][eE][0-9], [1-9][0-9].[0-9][eE][0-9], 3 combinations
  countDecimalExponents (n) {
    return NUM_ES * NUM_DIGITS ** BigInt(n - 3) * BigInt(n - 4) +
    (NUM_DIGITS - 1n) * NUM_ES * NUM_DIGITS ** BigInt(n - 3) * (BigInt(n - 4) * BigInt(n - 3) / 2n)
  }

  // E.g. "123.456E-789"
  // 0.[0-9][eE][+-][0-9]
  // [1-9].[0-9][eE][+-][0-9]
  countDecimalSignedExponents (n) {
    return NUM_ES * NUM_SIGNS * NUM_DIGITS ** BigInt(n - 4) * BigInt(n - 5) +
    (NUM_DIGITS - 1n) * NUM_ES * NUM_SIGNS * NUM_DIGITS ** BigInt(n - 4) * (BigInt(n - 5) * BigInt(n - 4) / 2n)
  }

  countNonNegativeNumbers (n) {
    let l = 0n
    if (n === 1) {
      l += 1n // "0"
    }
    l += this.countPositiveIntegers(n)
    if (n >= 3) {
      l += this.countDecimals(n)
      l += this.countExponents(n)
    }
    if (n >= 4) {
      l += this.countSignedExponents(n)
    }
    if (n >= 5) {
      l += this.countDecimalExponents(n)
    }
    if (n >= 6) {
      l += this.countDecimalSignedExponents(n)
    }
    return l
  }

  countNegativeNumbers (n) {
    return this.countNonNegativeNumbers(n - 1)
  }

  countNumbers (n) {
    let l = 0n
    l += this.countNonNegativeNumbers(n)
    if (n >= 2) {
      l += this.countNegativeNumbers(n)
    }
    return l
  }

  // Highly recursive, memoization is crucial here
  countStringInteriors = memoize(n => {
    if (n === 0) {
      return 1n
    }

    let l = 0n

    if (this.#encoding === 'raw') {
      if (n >= 1) {
        l += this.countStringInteriors(n - 1) * (
          NUM_1_BYTE_CODE_POINTS +
          NUM_2_BYTE_CODE_POINTS +
          NUM_3_BYTE_CODE_POINTS +
          NUM_SURROGATE_CODE_POINTS +
          NUM_4_BYTE_CODE_POINTS
        )
      }
    } else if (this.#encoding === 'utf32') {
      if (n >= 1) {
        l += this.countStringInteriors(n - 1) * (
          NUM_1_BYTE_CODE_POINTS +
          NUM_2_BYTE_CODE_POINTS +
          NUM_3_BYTE_CODE_POINTS +
          NUM_4_BYTE_CODE_POINTS
        )
      }
    } else if (this.#encoding === 'utf16') {
      if (n >= 1) {
        l += this.countStringInteriors(n - 1) * (
          NUM_1_BYTE_CODE_POINTS +
          NUM_2_BYTE_CODE_POINTS +
          NUM_3_BYTE_CODE_POINTS
        )
      }
      if (n >= 2) {
        l += this.countStringInteriors(n - 2) * NUM_4_BYTE_CODE_POINTS
      }
    } else if (this.#encoding === 'utf8') {
      if (n >= 1) {
        l += this.countStringInteriors(n - 1) * NUM_1_BYTE_CODE_POINTS
      }
      if (n >= 2) {
        l += this.countStringInteriors(n - 2) * NUM_2_BYTE_CODE_POINTS
      }
      if (n >= 3) {
        l += this.countStringInteriors(n - 3) * NUM_3_BYTE_CODE_POINTS
      }
      if (n >= 4) {
        l += this.countStringInteriors(n - 4) * NUM_4_BYTE_CODE_POINTS
      }
    } else {
      throw Error('bad encoding')
    }

    if (n >= 2) {
      l += this.countStringInteriors(n - 2) * NUM_ESCAPES
    }
    if (n >= 6) {
      l += this.countStringInteriors(n - 6) * NUM_HEX_ESCAPES
    }

    return l
  })

  countStrings (n) {
    return this.countStringInteriors(n - 2)
  }

  countArrayInteriorsK = memoize(k => {
    if (k === 0) {
      return n => this.#numWs ** BigInt(n)
    }

    if (k === 1) {
      return n => this.countElements(n)
    }

    return memoize(n => {
      // Try every possible location for the comma after the first element
      let l = 0n
      for (let i = 1; (k - 1) * 2 - 1 <= n - (i + 1); i++) {
        l += this.countElements(i) * this.countArrayInteriorsK(k - 1)(n - (i + 1))
      }
      return l
    })
  })

  countArrayInteriors = memoize(n => {
    // Try every possible number of array elements
    let l = 0n
    for (let k = 0; k * 2 - 1 <= n; k++) {
      l += this.countArrayInteriorsK(k)(n)
    }
    return l
  })

  countArrays (n) {
    return this.countArrayInteriors(n - 2)
  }

  // A key is a whitespaced string
  countKeys = memoize(n => {
    // Try every possible size of key
    let l = 0n
    for (let w = 0; w < n; w++) {
      l += this.countStrings(n - w) * this.#numWs ** BigInt(w) * BigInt(w + 1)
    }
    return l
  })

  countMembers = memoize(n => {
    // Try every possible location for the colon between the key and value
    let l = 0n
    for (let i = 2; i + 1 < n; i++) {
      l += this.countKeys(i) * this.countElements(n - (i + 1))
    }
    return l
  })

  countObjectInteriorsK = memoize(k => {
    if (k === 0) {
      return n => this.#numWs ** BigInt(n)
    }

    if (k === 1) {
      return n => this.countMembers(n)
    }

    return memoize(n => {
      // Try every possible location for the comma after the first key and value
      let l = 0n
      for (let i = 4; (k - 1) * 5 - 1 <= n - (i + 1); i++) {
        l += this.countMembers(i) * this.countObjectInteriorsK(k - 1)(n - (i + 1))
      }
      return l
    })
  })

  countObjectInteriors = memoize(n => {
    // Try every possible number of key-value pairs
    let l = 0n
    for (let k = 0; 5 * k - 1 <= n; k++) {
      l += this.countObjectInteriorsK(k)(n)
    }
    return l
  })

  countObjects (n) {
    return this.countObjectInteriors(n - 2)
  }

  countValues = memoize(n => {
    let l = 0n
    if (n === 4) {
      l += 2n // "null", "true"
    }
    if (n === 5) {
      l += 1n // "false"
    }
    if (n >= 1) {
      l += this.countNumbers(n)
    }
    if (n >= 2) {
      l += this.countStrings(n)
      l += this.countArrays(n)
      l += this.countObjects(n)
    }
    return l
  })

  countElements = memoize(n => {
    // Try every possible size of value
    let l = 0n
    for (let w = 0; w < n; w++) {
      l += this.countValues(n - w) * this.#numWs ** BigInt(w) * BigInt(w + 1)
    }
    return l
  })
}

Example usage:

import { Counter } from './jsoncount.js'

const counter8 = new Counter(true, 'utf8')

for (let n = 0; n <= 10; n++) {
  console.log(n, counter8.countElements(n))
}