Change json. stringify to js.stringify

Json.stringify is used to serialize A JS variable into a JSON string. In general, this is fine for common use, but once the requirements exceed the JSON standard, there will be problems. For example, as mentioned in the previous article, you need to serialize any JS variable for presentation.

Serialization of undefined, Function, NaN, Symbol, BigInt, and the handling of looping referenced objects will be addressed. Transform json.stringify to js.stringify step by step. It is recommended to pull straight to the bottom to see the complete code, and then look back at the idea, explanation.

By default, json. stringify will:

ignoreundefined.Function.Symbol.
willNaN.Infinity.-InfinityConverted tonull
encounterBigIntAn error is thrown.

Now requirements, hopefully they will be processed into:

undefiend: undefiend
Function: <Function>
Symbol(123): Symbol(123)
NaN: NaN
Infinity: Infinity
-Infinity: -Infinity
BigInt(123): 123n

Create a test case

const obj = {
  undefined: undefined.Function: () = > {},
  Symbol: Symbol(123),
  NaN: NaN.Infinity: Infinity.'-Infinity': -Infinity.BigInt: 123n,}Copy the code

Simple type handling

For those who don’t know, json.stringify also has two optional arguments, and adding type handling will use the second replacer argument. See json.stringify () -mdn for details on replacer. (Replacer has two overloads, and we will only consider replacer as a function in the future)

The replacer is then passed a function to handle the variables. The replacer is executed before serialization, and the return value of the replacer is taken as the serialization argument.

Let’s get started.

String replacers

/* Replacer */ to be implemented later
function jsReplacer(key, value) {
  return value
}

/* replacers */
function serializer(. replacers) {
  const _replacers = replacers.filter((replacer) = >!!!!! replacer)return function (key, value) {
    return _replacers.reduce((value, replacer) = > {
      return replacer.call(this, key, value)
    }, value)
  }
}

function jsStringify(value, replacer, space) {  
  return JSON.stringify(value, serializer(replacer, jsReplacer), space)
}

jsStringify(obj)
Copy the code

The Serializer is used to connect the jsreplacers to the replacers. The equivalent of

function newReplacer(key, value) {
  return jsReplacer(key, replacer(key, value)) 
}
Copy the code

In addition, in json. stringify, replacer’s this points to the parent object of value, so we need to bind this to the concatenated function via call.

jsReplacer

function jsReplacer(key, value) {
  switch (typeof value) {
    case 'undefined':
      return 'undefined'
    case 'function':
      return '<Function>'
    case 'number':
      if (Number.isNaN(value)) return 'NaN'
      if (value === Infinity) return 'Infinity'
      if (value === -Infinity) return '-Infinity'
      return value
    case 'symbol':
      return value.toString()
    case 'bigint':
      return `${value}n`
      default:
      // Other types are serialized without processing
      return value
  }
}
Copy the code

We need to convert unsupported types into supported types in jsReplacer and return json.stringify for serialization. It’s usually a string.

Combining the above code and running the test case yields:

{
  "undefined": "undefined"."Function": "<Function>"."Symbol": "Symbol(123)"."NaN": "NaN"."Infinity": "Infinity"."-Infinity": "-Infinity"."BigInt": "123n"
}
Copy the code

They were all handled successfully. But if they’re all treated as strings, they’ll be confused with strings and indistinguishable from each other.

Next, let’s get rid of the extra double quotes.

Remove extra double quotes

Using replacer alone we can’t get rid of extra double quotes, but we can reprocess serialized strings.

Json.stringify returns us a string in which we need to find our prey. To be able to distinguish our prey from normal prey, we tag our prey before we release it.

tag

const SIGN = Date.now()
const LEFT_MARK = ` __${SIGN}`
const RIGHT_MARK = `${SIGN}__ `
Copy the code

Start by creating two tags to wrap the prey. LEFT_MARK and RIGHT_MARK can be any string, you just have to make them special enough. Add date.now () as the signature.

function mark(text) {
  return `${LEFT_MARK}${text}${RIGHT_MARK}`
}
Copy the code

Write a mark function to mark the prey by adding LEFT_MARK and RIGHT_MARK to the left and right sides.

function jsReplacer(key, value) {    
  switch (typeof value) {
    case 'undefined':
      return mark('undefined')
    case 'function':
      return mark('<Function>')
    case 'number':
      if (Number.isNaN(value)) return mark('NaN')
      if (value === Infinity) return mark('Infinity')
      if (value === -Infinity) return mark('-Infinity')
      return value
    case 'symbol':
      return mark(value.toString())
    case 'bigint':
      return mark(`${value}n`)
    default:
      return value
  }
}
Copy the code

Mark is used to mark prey in jsReplacer.

identify

Use the re to match the tag to get our prey:

const REGEXP = new RegExp(`${LEFT_MARK}(. *?)${RIGHT_MARK}`.'g')
Copy the code

Since the string we processed in jsReplacer is overquoted when delivered to json.stringify serialization, we need to put quotes around it when we match.

const REGEXP = new RegExp(`"${LEFT_MARK}(. *?)${RIGHT_MARK}"`.'g')
Copy the code

replace

function unmark(text) {
  return text.replace(REGEXP, '$1')}Copy the code

Replace prey with unquoted with string.prototype. replace.

The complete code

const SIGN = Date.now()
const LEFT_MARK = ` __${SIGN}`
const RIGHT_MARK = `${SIGN}__ `
const REGEXP = new RegExp(`"${LEFT_MARK}(. *?)${RIGHT_MARK}"`.'g')

function mark(text) {
  return `${LEFT_MARK}${text}${RIGHT_MARK}`
}

function unmark(text) {
  return text.replace(REGEXP, '$1')}function jsReplacer(key, value) {    
  switch (typeof value) {
    case 'undefined':
      return mark('undefined')
    case 'function':
      return mark('<Function>')
    case 'number':
      if (Number.isNaN(value)) return mark('NaN')
      if (value === Infinity) return mark('Infinity')
      if (value === -Infinity) return mark('-Infinity')
      return value
    case 'symbol':
      return mark(value.toString())
    case 'bigint':
      return mark(`${value}n`)
    default:
      return value
  }
}

function serializer(. replacers) {
  const _replacers = replacers.filter((replacer) = >!!!!! replacer)return function (key, value) {
    return _replacers.reduce((value, replacer) = > {
      return replacer.call(this, key, value)
    }, value)
  }
}

function jsStringify(value, replacer, space) {
  const replacers = serializer(replacer, jsReplacer)
  const reuslt = JSON.stringify(value, replacers, space)
  return unmark(reuslt)
}
Copy the code

Running the test case at this point we should get:

{
  "undefined": undefined,
  "Function": <Function>,
  "Symbol": Symbol(123),
  "NaN": NaN,
  "Infinity": Infinity,
  "-Infinity": -Infinity,
  "BigInt": 123n
}
Copy the code

Resolves object circular references

With the above code, you can handle all types, but you can still throw an error for objects that are referred to in a loop.

Create a test case

const obj = {
  parent: {},
  child: {},
}
obj.child.parent = obj.parent
obj.parent.child = obj.child
Copy the code

Simplifies to a binary tree

The object is also a tree and can be thought of in the simplest binary tree.

Turn the problem into an algorithmic one, “Verifying parent-child unequal binary trees”.

Algorithm subject

Given a binary tree, determine whether it is a valid parent-child unequal binary tree.

Suppose a parent-child unequal binary tree has the following characteristics:

The value of any node is not equal to the value of its parent node at any location.
The value of all children of the current node is not equal to the value of the current node.

The above two features are the same meaning, different ways of expression

Example 1

Input: 1 / \ 2 2 Output: trueCopy the code

Example 2

Input: 1 / \ 2 3 / \ 1 4 Output: falseCopy the code

Answer key

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
function isValidTree(root) {
  const stack = []
  
  function helper(node) {
    if (node === null) return true
    
    const nodeIndex = stack.indexOf(node.val)
    if (~nodeIndex) return false
    
    stack.push(node.val)
    const res = helper(node.left) && helper(node.right)
    stack.pop()
    return res
  }
  
  return helper(root)
}
Copy the code

If you have a valid tree, its left and right subtrees are also valid independently. In turn, we need to know whether a tree is valid, we need to know whether its left and right subtrees are valid, but whether the left subtree is valid has nothing to do with the right subtree, just the parent tree and its own subtrees. Therefore, a depth-first search method should be used for traversal.

To determine the validity of the lowest node, we need to collect all of its parents. Therefore, we need to create a stack to store the parent node, push the current node onto the stack when it is accessed, and push the current node off the stack when its children are accessed.

Json.stringify’s replacer is a depth-first search, so you can solve the problem of circular references directly with the replacer.

Simulate json.stringify internal logic

However, replacer is a little different from the above solution. Replacer does not know the child node, only the parent node of the current node (via this). Therefore, we need to modify the above algorithm.

function isValidTree(root) {
  const stack = []
  let result = true
  function helper(node) {
    if (node === null) return null
    
    // This = the parent of node
    // This is the verified parent or root node
    
    const thisIndex = stack.indexOf(this.val)
    if (~thisIndex) {
      // If this.val already exists in stack
      // verify the right subtree of this
      // Remove the left subtree after this
      stack.splice(thisIndex + 1)}else {
      // If this.val does not exist in stack
      // verify the left subtree of this
      stack.push(this.val)
    }
    
    // The current stack contains information about all parent nodes of a node
    const nodeIndex = stack.indexOf(node.val)
    if (~nodeIndex) {
      // If node.val already exists in stack
      // Indicates that the tree is not a parent unequal tree
      result = false
      // Returns null to prevent a search for the children of the current node
      return null
    }

    return node
  }
  
  /* Simulate json.stringify internal traversal */
  // The return value of the helper will be the node for the next serch
  // The operation cannot be interrupted. The helper can only return NULL to prevent the search for child nodes
  function search(node) {
    if (node === null) return
    
    const left = helper.call(node, node.left)
    search(left)
    
    const right = helper.call(node, node.right)
    search(right)
  }
  search(root)
  
  return result
}
Copy the code

Convert replacer

function createCircularReplacer() {
  const stack = []

  return function (key, value) {
    const thisIndex = stack.indexOf(this)
    if (~thisIndex) {
      stack.splice(thisIndex + 1)}else {
      stack.push(this)}const valueIndex = stack.indexOf(value)
    if (~valueIndex) return '<Circular>'
    
    return value
  }
}

function serializer(. replacers) {
  const _replacers = replacers.filter((replacer) = >!!!!! replacer)return function (key, value) {
    return _replacers.reduce((value, replacer) = > {
      return replacer.call(this, key, value)
    }, value)
  }
}

function jsStringify(value, replacer, space) {
  const replacers = serializer(replacer, createCircularReplacer())
  const result = JSON.stringify(value, replacers, space)
  return result
}
Copy the code

CircularReplacer logic is pushed outside by closures, and the createCircularReplacer returns the same value as the previous helper. Other basic and above one – by – one correspondence, contrast to see it is easy to understand.

Adding a Path Record

The above returns

only know that they form a Circular reference, but not where they form a loop to where.

Just add another key in a similar way to the stack.

function createCircularReplacer() {
  const stack = []
  const keys = []
  
  function circulerText(key, value) {
    const valueIndex = stack.indexOf(value) // Get the same parent node location as value
    const path = keys.slice(0, valueIndex + 1) // Get the full path to the parent node
    return `<Circular ${path.join('. ')}> `
  }

  return function (key, value) {
    if (stack.length === 0) {
      // When stack is empty, value is the root node
      // Subsequent processing can be skipped
      // We do not need the parent of the root node
      stack.push(value)
      keys.push('~') // Use ~ as the key of the root node
      return value
    }
    
    const thisIndex = stack.indexOf(this)
    if (~thisIndex) {
      stack.splice(thisIndex + 1)
      keys.splice(thisIndex + 1)}else {
      stack.push(this)}// The key of value cannot be obtained when value is the parent node
    // Add the key to the keys while the key is still known
    // so keys represent the keys of all parent nodes and their own nodes
    keys.push(key)

    const valueIndex = stack.indexOf(value)
    if (~valueIndex) return circulerText(key, value)
    
    return value
  }
}
Copy the code

Run the test case after merging the code:

{
  "parent": {
    "child": {
      "parent": "<Circular ~.child>"}},"child": {
    "parent": {
      "child": "<Circular ~.parent>"}}}Copy the code

Pretty much as expected,

And then do it the same way we did earlier to remove the extra double quotes,

I think it’s perfect.

The complete code

const SIGN = Date.now()
const LEFT_MARK = ` __${SIGN}`
const RIGHT_MARK = `${SIGN}__ `
const REGEXP = new RegExp(`"${LEFT_MARK}(. *?)${RIGHT_MARK}"`.'g')

function mark(text) {
  return `${LEFT_MARK}${text}${RIGHT_MARK}`
}

function unmark(text) {
  return text.replace(REGEXP, '$1')}function jsReplacer(key, value) {    
  switch (typeof value) {
    case 'undefined':
      return mark('undefined')
    case 'function':
      return mark('<Function>')
    case 'number':
      if (Number.isNaN(value)) return mark('NaN')
      if (value === Infinity) return mark('Infinity')
      if (value === -Infinity) return mark('-Infinity')
      return value
    case 'symbol':
      return mark(value.toString())
    case 'bigint':
      return mark(`${value}n`)
    default:
      return value
  }
}

function createCircularReplacer() {
  const stack = []
  const keys = []
  
  function circulerText(key, value) {
    const valueIndex = stack.indexOf(value)
    const path = keys.slice(0, valueIndex + 1)
    return mark(`<Circular ${path.join('. ')}> `)}return function (key, value) {
    if (stack.length === 0) {
      stack.push(value)
      keys.push('~')
      return value
    }
    
    const thisIndex = stack.indexOf(this)
    if (~thisIndex) {
      stack.splice(thisIndex + 1)
      keys.splice(thisIndex + 1)}else {
      stack.push(this)
    }
    keys.push(key)

    const valueIndex = stack.indexOf(value)
    if (~valueIndex) return circulerText(key, value)
    
    return value
  }
}

function serializer(. replacers) {
  const _replacers = replacers.filter((replacer) = >!!!!! replacer)return function (key, value) {
    return _replacers.reduce((value, replacer) = > {
      return replacer.call(this, key, value)
    }, value)
  }
}

function jsStringify(value, replacer, space) {
  const replacers = serializer(replacer, createCircularReplacer(), jsReplacer)
  const reuslt = JSON.stringify(value, replacers, space)
  return unmark(reuslt)
}
Copy the code

Change json. stringify to js.stringify

Create a test case

Simple type handling

String replacers

jsReplacer

Remove extra double quotes

tag

identify

replace

The complete code

Resolves object circular references

Create a test case

Simplifies to a binary tree

Algorithm subject

Example 1

Example 2

Answer key

Simulate json.stringify internal logic

Convert replacer

Adding a Path Record

The complete code

Related Posts

XSS and CSRF

Relearn front end (4) – data structures and algorithms

TypeScript