preface

This article shares a solution to a problem that has puzzled the author for a long time.

The cause of

As a new feature of ES6, Set/WeakSet/Map/WeakMap is a common high frequency knowledge point in the interview, and often asked is nothing more than: the corresponding method, and Obejct/Array differences, and the relationship between them. These are very basic knowledge points, if you are not clear friends can refer to Ruan Yifeng teacher ES6 introduction tutorial.

In a previous interview, the author was also asked these questions. After answering the basic knowledge above, the interviewer casually asked: If you want to achieveWeakMap 的 polyfillAny good ideas? My reaction to the question was something like this:In my previous understanding,MapEtc data structures should be andProxySimilarly, these are low-level implementations, never thinking that there could be equivalents for these grammarspolyfill. Well, if we ask, there must be a way to do that. In the next 30 seconds or so of reflection, some things like weak references,HashTable,O(1)Words like time complexity fly through my mind…… In the end, we failed to come up with an effective solution.

The original idea

To implement WeakMap, Map must be implemented first. On the basis of the latter implementation, key can only be an object and weak reference can be realized. The Map has to support objects as keys and has to implement the O(1) time complexity of lookup. We know that the key of an object in JavaScript can only be a String or Symbol; all other types implicitly call the corresponding.tostring () method to convert toString. The O(1) complexity query cannot be realized with array storage. Even if there were other ways to implement maps, weak references would be completely impossible (before ES2021). So THERE was a time when I thought this was an unsolvable problem.

As for the realization of weak reference, ES2021 introduced WeakRef, which can preserve a weak reference to another object without preventing the weak reference object from being recycled by GC. Our thoughts today have nothing to do with that feature.

Back to the question

If you recall carefully, what the interviewer asked me at that time was polyfill that implemented WeakMap, but did not require Map. In addition, compared with Map, WeakMap has some important characteristics:

  • Keys must be objects
  • There is nokeys()/values()/entries()Wait for the traversal method, there is nosizeattribute
  • Does not supportclear()methods

That means WeakMap only has four methods available: get()/set()/has()/delete(). These methods have one thing in common, that is, the first input parameter is key. Imagine: when we know which object to add attributes to, can we add attributes directly to the specified object? The same is true for search and delete, which indirectly implements weak references because it does not directly reference the object.

Following this idea, a polyfill meeting the requirements was completed

implementation

Take a look at the WeakMap interface in typescript

interface WeakMap<K extends object, V> {
  delete(key: K): boolean
  get(key: K): V | undefined
  has(key: K): boolean
  set(key: K, value: V): this
}
interface WeakMapConstructor {
    new <K extends object = object, V = any>(entries? :readonly [K, V][] | null) :WeakMap<K, V>;
    readonly prototype: WeakMap<object.any>;
}
Copy the code

In the interface definition, we can clearly see the parameters and return values of each method. Next, I am going to use ES6 class syntax to do this:

The code structure

class WeakMap<K extends object = object, V = any> implements WeakMap<K, V> {
    private uid: symbol
    constructor (entries? :readonly [K, V][] | null | undefined) {}
    // Object type protection function, whether is a valid key value
    private isLegal(o: unknown): o is object {
    	return Object(o) === o
    }
    delete (key: K): boolean {}
    get(key: K): undefined | V {}
    has(key: K): boolean {}
    set(key: K, value: V): this{}}Copy the code

The above is the overall structure of the class, including common methods, internal attributes, and corresponding curd methods. Next, we will implement the corresponding method body……

constructor

.constructor (entries? :readonly [K, V][] | null | undefined) {
  this.uid = Symbol('WeakMap')
  if(entries ! = =undefined&& entries ! = =null) {
    if (typeof entries[Symbol.iterator] === 'function') {
      try {
        for (const [key, value] of entries) {
          this.set(key, value)
        }
      } catch {
        throw TypeError(`Iterator value a is not an entry object`)}}else {
      throw TypeError(
        `${entries} is not iterable (cannot read property Symbol(Symbol.iterator))`)}}}...Copy the code

In the constructor we do two things altogether:

The unique identity of the generated instance

Here we use Symbol as the identifier, so that we can bind the property to the specified key value object as our polyfill ‘private property’, mainly using the characteristics of Symbol: Symbol(‘WeakMap’)! == Symbol(‘WeakMap’) so that defined properties cannot be obtained by other methods.

Polyfill should theoretically be implemented using pre-ES6 syntax, but FOR the sake of explanation, I decided to use Symbol. Of course, concatenating random strings as UID has the same effect.

Binding Symbol attribute, although not directly access or traversal, but can be by Object. GetOwnPropertySymbols (target) to get to…

Processing into

As you can see from the interface definition given, an iterable object can be passed as an argument when constructing an instance object. The first element of the object is key, and the second element is value. We simply iterate over the object and call set to bind it.

The format of the input parameter must be an iterable, that is, an object with the Symbol. Iterator property deployed, and depending on the actual result, different errors are thrown.

The test results are not necessarily accurate

set

The first input parameter of the set method is a weak reference and must be the key of the object, the second input parameter is the value of the binding, and returns the this of the current instance to support the chained call.

. set (key: K,value: V): this {
  // If the key value is not an object, a type error is thrown
  if (!this.isLegal(key)) {
    throw TypeError('Invalid value used as weak map key')}// Change the original value when already set
  if (this.uid in key) {
    const entry = key[this.uid]
    entry[1] = value
    return this
  }
  Object.defineProperty(key, this.uid, {
    value: [key, value],
    configurable: true.writable: true.enumerable: false
  })
  return this}...Copy the code

When setting the value via Object.defineProperty, be sure to set enumerable to false so that the original Object doesn’t pick up the property in the normal traversal method.

has

The HAS method passes in the key and returns Boolean, false if the key type is wrong or not set

. has (key: K) {if (!this.isLegal(key)) return false
  if (key.hasOwnProperty(this.uid)) return true
  return false}...Copy the code

get

The get method passes in the key value to get, and returns undefined if the key is an invalid key or not set, or the corresponding value otherwise

. get(key: K):undefined | V {
  if (!this.isLegal(key)) return undefined
  if(! key.hasOwnProperty(this.uid)) return undefined
  const entry = key[this.uid]
  return entry[1]}...Copy the code

delete

The delete method passes in the key to delete, returning false if the key is an invalid key or if it is not set, and true otherwise

delete(key: K) {
  if (!this.isLegal(key)) return false
  if(! key.hasOwnProperty(this.uid)) return false
  delete key[this.uid]
  return true
}
Copy the code

Type supplement

Finally, we need to append the specified type to the instance of the object.

In the JavaScript Object. The prototype. ToString is the most common way for judging types. WeakMap instance is of type [Object WeakMap], so we also need to add it to our class

Object.defineProperty(WeakMap.prototype, Symbol.toStringTag, {
  value: 'WeakMap'
})
Copy the code

About why defining Symbol. ToStringTag for Object binding Object. The prototype. ToString access type, unclear friend can look at the official documentation

One thing to note here is that we need to define symbol.toStringTag on the prototype, not directly in the class as an attribute, because this is an attribute of the prototype and not an instance attribute.

test

const weakMap = new WeakMap<object.any> ()// new an instance
const o = {
	name: 'juejin'
}
weakMap.set(o, 'done')
weakMap.get(o)   // done
weakMap.has(o)   // true
Copy the code

WeakMap(Polyfill) instance structure

Object that is the Key value

conclusion

So far, we have realized a simple WeakMap, although it does not really simulate its data structure, but it can also use the characteristics of WeakMap to achieve its functions, the same way can also achieve the polyfill of WeakSet.

There is no idea how to simulate the Map/Set structure. Ideas of the big guy welcome to comment on the area!

reference

ES6 Tutorial