hjava

hjava 查看完整档案

北京编辑华中科技大学  |  信息安全 编辑美团  |  前端技术专家 编辑填写个人主网站
编辑

大象Web老油条,专治疑难杂症
美团招前端,欢迎找我内推~

个人动态

hjava 赞了文章 · 2020-12-11

should.js原理浅析

背景

should.js是一个比较全的代码测试库,无关框架,引入就可使用,使用起来很方便

使用注意事项和原理浅析

在使用时,引入should.js后,如果你的对象是通过Object.create(null)来创建的,操作如下,该对象.should就不存在
image.png
如果是通过正常的创建对象,就可以使用 .should
image.png

  • 下面说一下为什么会出现这样的问题呢?

首先,用Object.create()来创建对象,会把新创建对象的__proto__指向的对象原型设置为传进Object.create中的对象,比如上面的
let obj2 = Object.create(null)
这里就会把obj2的原型对象设置为null,此时obj2就不能继承基类Object的方法和属性,也就不能使用.should了

  • 那么问题来了,为什么按照这种方式let obj2 = Object.create(null)创建对象就不能使用.should了呢?

这里就需要说一下should.js是如何添加到基类Object中的
首先看一下这段代码
image.png
其中红框中的代码就是如何把should添加到Object中的,这里是通过使用Object.defineProperty来实现的,这也就是为什么上面第一种方式创建的对象不能够.should了,而第二种方式就可以拿到Object的原型上的should

下面我们看一下上图中的should$1是怎么来的
image.png
当然代码中的一些工具方法也会给到should$1,比如:
image.png
这里方法时干什么的就不在这里细说啦,感兴趣的友友们可以自行看下源码哈!
should$1返回了一个Assertion的实例,那么我们看一下Assertion是什么玩意
image.png

Assertion中的方法如下
image.png
在上图Assertion返回的方法中,我们能看到有一个should对象,点开里面还是一个should对象,一层一层嵌套进去,那么它是如何实现should的链式调用的呢?以及它里面的方法时如何添加进去的呢?请看下面这个图:
image.png
在这里有一个addChainf的方法,传入需要name和onCall,这里的name就是需要添加的属性,onCall就是这个属性的描述函数,通过这种方式把should中的方法添加进来,放到should的原型上,后续可以通过原型链的方式调用这些方法。这个方法执行后每次都会返回一个this,就是它本身,因此就实现了should的链式调用。
image.png

小结

  • should里面实现了链式调用,我们上次看的promiz中也实现了链式调用,这两个库实现链式调用还是不一样的,promiz中是在自己的构造函数中返回一个promise属性是自己,而should是通过使用Object.defineProperty的方式直接挂到对象的原型上来实现的,这样做的好处就是基于Object基类的其他类型都可以调用should,比如String、Function、Number等
  • should.js的断言也很语义化,很好理解
查看原文

赞 1 收藏 0 评论 0

hjava 赞了文章 · 2020-12-11

should.js初探

一、概述

背景

为了提高个人基础能力,学习优秀项目的设计和代码编写方式,因此学习should.js的源码并进行分析

什么是should.js


should is an expressive, readable, framework-agnostic assertion library.

should.js是一个表现力强、可读性强、与框架无关的断言库。Node.js自带的断言库Assert,10 多个断言测试的函数,但是功能有限,而should.js可以让测试更加友好,因此一般前端的单元测试会引入should.js。

二、使用方法

示例

var should = require('should');

var user = {
    name: 'tj'
  , pets: ['tobi', 'loki', 'jane', 'bandit']
};

user.should.have.property('name', 'tj');
user.should.have.property('pets').with.lengthOf(4);

// if the object was created with Object.create(null)
// then it doesn't inherit `Object` and have the `should` getter
// so you can do:

should(user).have.property('name', 'tj');
should(true).ok;

someAsyncTask(foo, function(err, result){
  should.not.exist(err);
  should.exist(result);
  result.bar.should.equal(foo);
});

使用方法


1、安装

$ npm install should --save-dev

2、使用

var should = require('should');

(5).should.be.exactly(5).and.be.a.Number;

三、项目结构介绍

项目目录


image.png

四、源码分析

index.js

项目入口文件,导出node.js

/lib/node.js


var should = require('./should');

should
  .use(require('./ext/assert'))
  .use(require('./ext/chain'))
  .use(require('./ext/bool'))
  .use(require('./ext/number'))
  .use(require('./ext/eql'))
  .use(require('./ext/type'))
  .use(require('./ext/string'))
  .use(require('./ext/property'))
  .use(require('./ext/http'))
  .use(require('./ext/error'))
  .use(require('./ext/match'))
  .use(require('./ext/deprecated'));

 module.exports = should;

引入should.js,然后use方法引入ext文件夹下的扩展方法,便于在测试过程中使用引入的扩展方法。最后导出should。下面我们先介绍should。

/lib/should.js


/**
 * Our function should
 * @param obj
 * @returns {Assertion}
 */
var should = function(obj) {
  return new Assertion(util.isWrapperType(obj) ? obj.valueOf(): obj);
};

/**
 * Initialize a new `Assertion` with the given _obj_.
 *
 * @param {*} obj
 * @api private
 */

var Assertion = should.Assertion = function Assertion(obj) {
  this.obj = obj;
};

...
exports = module.exports = should;

should方法返回一个新的Assertion实例,而Assertion断言函数通过传递的obj参数初始化,并在Assertion的原型上定义assert、getMessage、copy、copyIfMissing方法。

接下来定义扩展断言函数的方法:add、alias,它使用了一些逻辑只定义肯定的断言和否定的断言本身的规则。所有的动作都发生在子文本中,这种方法考虑的是否定。我们可以添加一些不依赖于断言状态的修饰符。

通过util为should定义断言错误、format和use方法,最后将should导出,便于前端进行单元测试时通过require将其引入。其中uti文件中定义了项目中用到的一些函数,例如判断参数是否是字符串、将b对象属性复制到a对象并返回a对象的merge方法等。

/lib/ext/assert.js


将assert暴露给should,通过util文件中的merge方法将asset中的方法定义在should上,这样在使用的过程中不必使用require()的方法再将asset模块引入。

为should定义exist方法,用于判断传入的第一个参数是否是null,同时在第一个参数是null时抛出错误显示第二个参数给定的信息。should.not.exist方法则定义当传入的第一个参数不是null时报错。

/lib/ext/chain.js


module.exports = function(should, Assertion) {

  function addLink(name) {
    Object.defineProperty(Assertion.prototype, name, {
      get: function() {
        return this;
      }
    });
  }

  ['an', 'of', 'a', 'and', 'be', 'have', 'with', 'is', 'which', 'the'].forEach(addLink);
};

对'an', 'of', 'a', 'and', 'be', 'have', 'with', 'is', 'which', 'the'词语通过addLink方法定义到Assert原型上,使得Assertion也包含这些属性,并且返回Assertion对象本身,实现should的链式调用。

源码学习小结


  • should.js的文件结构设计合理,例如将should的扩展方法统一放到ext文件夹下面,并且根据功能单独存放到文件中,这样不仅结构清晰,并且模块化的方式提高代码的复用性,也增强了项目的扩展性
  • 项目通过chain.js文件中的方法实现了Assertion的链式调用

五、总结

should.js项目结构非常清晰,虽然和之前学习的axios、promise等项目相比,代码量稍多,但是根据项目结构阅读起来也不会存在特别大的难度。should.js非常语义化,感觉像是使用英文写自然语言一样写测试,上手容易并且容易阅读,推荐使用should.js进行前端单元测试。

查看原文

赞 1 收藏 0 评论 0

hjava 发布了文章 · 2020-11-29

JavaScript数字运算必备库——big.js源码解析

概述

在我们常见的JavaScript数字运算中,小数和大数都是会让我们比较头疼的两个数据类型。

  • 在大数运算中,由于number类型的数字长度限制,我们经常会遇到超出范围的情况。比如在我们传递Long型数据的情况下,我们就只能把它转换到字符串进行传递和处理。
  • 而在小数点数字进行运算的过程中,JavaScript又由于它的数据表示方式,从而导致了小数运算会有不准确的情况。最经典的一个例子就是0.3-0.2,并不等于0.1,而是等于0.09999999999999998。

在之前的博客中我介绍了一个Long类型数据处理的库,叫做long.js,它能够比较有效地处理弄型数据。从而扩展JavaScript在数据类型中的一个处理能力,大家如果感兴趣的话可以去看一下这篇文章:如何在JavaScript中实现一个Long型——Long.js源码学习与分析

今天我们需要介绍的这个库,它不仅仅能够支持处理Long类型的数据,也能够准确的处理小数的运算,他就是big.js

这个库历史也很悠久了,从commit记录来看,第一次提交还是在2012年。现在,它已经拥有了3.2K个star,这足以表明这个库受欢迎的程度。同时,这个库具有完备的单元测试,目前所有的issue都已经解决,所以大家也不用担心这个库的质量问题。

代码示例

首先,让我们来看下,big.js这个库到底是如何使用的,具体有哪些应用的场景和功能。

 x = new Big(123.4567)
 y = Big('123456.7e-3')                 // 'new' is optional
 z = new Big(x)
 x.eq(y) && x.eq(z) && y.eq(z)
 ​
 ​
 0.3 - 0.1                              // 0.19999999999999998
 x = new Big(0.3)
 x.minus(0.1)                           // "0.2"
 x                                      // "0.3"

 function Big(n) {
  var x = this;
 ​
  // 支持函数调用方式进行初始化,可以不使用new操作符
  if (!(x instanceof Big)) return n === UNDEFINED ? _Big_() : new Big(n);
 ​
  // 原型链判断,确认传入值是否已经为Big类的实例
  if (n instanceof Big) {
  x.s = n.s;
  x.e = n.e;
  x.c = n.c.slice();
  } else {
  if (typeof n !== 'string') {
  if (Big.strict === true) {
  throw TypeError(INVALID + 'number');
  }
 ​
  // 确定是否为-0,如果不是,转化为字符串.
  n = n === 0 && 1 / n < 0 ? '-0' : String(n);
  }
 ​
  // parse函数只接受字符串参数
  parse(x, n);
  }
 ​
  x.constructor = Big;
 }

 function parse(x, n) {
  var e, i, nl;
 ​
  if (!NUMERIC.test(n)) {
  throw Error(INVALID + 'number');
  }
 ​
  // 判断符号,是正数还是负数
  x.s = n.charAt(0) == '-' ? (n = n.slice(1), -1) : 1;
 ​
  // 判断是否有小数点
  if ((e = n.indexOf('.')) > -1) n = n.replace('.', '');
 ​
  // 判断是否为科学计数法
  if ((i = n.search(/e/i)) > 0) {
 ​
  // 确定指数值
  if (e < 0) e = i;
  e += +n.slice(i + 1);
  n = n.substring(0, i);
  } else if (e < 0) {
 ​
  // 是一个正整数
  e = n.length;
  }
 ​
  nl = n.length;
 ​
  // 确定数字前面有没有0,例如0123这种0
  for (i = 0; i < nl && n.charAt(i) == '0';) ++i;
 ​
  if (i == nl) {
 ​
  // Zero.
  x.c = [x.e = 0];
  } else {
 ​
  // 确定数字后面的0,例如1.230这种0
  for (; nl > 0 && n.charAt(--nl) == '0';);
  x.e = e - i - 1;
  x.c = [];
 ​
  // 把字符串转换成数组进行存储,这个时候已经去掉了前面的0和后面的0
  for (e = 0; i <= nl;) x.c[e++] = +n.charAt(i++);
  }
 ​
  return x;
 }

 P.plus = P.add = function (y) {
  var t,
  x = this,
  Big = x.constructor,
  a = x.s,
  // 所有操作均转化为两个Big类的实例进行运算,方便处理
  b = (y = new Big(y)).s;
 ​
  // 判断符号是不是不相等,即一个为正,一个为负
  if (a != b) {
  y.s = -b;
  return x.minus(y);
  }
 ​
  var xe = x.e,
  xc = x.c,
  ye = y.e,
  yc = y.c;
 ​
  // 判断是否某个值是0
  if (!xc[0] || !yc[0]) return yc[0] ? y : new Big(xc[0] ? x : a * 0);
 ​
  // 拷贝一份数组,避免影响原实例
  xc = xc.slice();
 ​
  // 填0来保证运算时的位数相等
  // 注意,reverse函数比unshift函数快
  if (a = xe - ye) {
  if (a > 0) {
  ye = xe;
  t = yc;
  } else {
  a = -a;
  t = xc;
  }
 ​
  t.reverse();
  for (; a--;) t.push(0);
  t.reverse();
  }
 ​
  // 把xc放到一个更长的数组中,方便后续循环加法操作
  if (xc.length - yc.length < 0) {
  t = yc;
  yc = xc;
  xc = t;
  }
 ​
  a = yc.length;
 ​
  // 执行加法操作,将数值保存到xc中
  for (b = 0; a; xc[a] %= 10) b = (xc[--a] = xc[a] + yc[a] + b) / 10 | 0;
 ​
  // 不需要检查0,因为 +x + +y != 0 ,同时 -x + -y != 0
 ​
  if (b) {
  xc.unshift(b);
  ++ye;
  }
 ​
  // 删除结尾的0
  for (a = xc.length; xc[--a] === 0;) xc.pop();
 ​
  y.c = xc;
  y.e = ye;
 ​
  return y;
 };

 P.times = P.mul = function (y) {
  var c,
  x = this,
  Big = x.constructor,
  xc = x.c,
  yc = (y = new Big(y)).c,
  a = xc.length,
  b = yc.length,
  i = x.e,
  j = y.e;
 ​
  // 符号比较确定最终的符号是为正还是为负
  y.s = x.s == y.s ? 1 : -1;
 ​
  // 如果有一个值是0,那么返回0即可
  if (!xc[0] || !yc[0]) return new Big(y.s * 0);
 ​
  // 小数点初始化为x.e+y.e,这是我们在两个小数相乘的时候,小数点的计算规则
  y.e = i + j;
 ​
  // 这一步也是保证xc的长度永远不小于yc的长度,因为要遍历xc来进行运算
  if (a < b) {
  c = xc;
  xc = yc;
  yc = c;
  j = a;
  a = b;
  b = j;
  }
 ​
  // 用0来初始化结果数组
  for (c = new Array(j = a + b); j--;) c[j] = 0;
 ​
  // i初始化为xc的长度
  for (i = b; i--;) {
  b = 0;
 ​
  // a是yc的长度
  for (j = a + i; j > i;) {
 ​
  // xc的一位乘以yc的一位,得到最终的结果值,保存下来
  b = c[j] + yc[i] * xc[j - i - 1] + b;
  c[j--] = b % 10;
 ​
  b = b / 10 | 0;
  }
 ​
  c[j] = b;
  }
 ​
  // 如果有进位,那么就调整小数点的位数(增加y.e),否则就删除最前面的0
  if (b) ++y.e;
  else c.shift();
 ​
  // 删除后面的0
  for (i = c.length; !c[--i];) c.pop();
  y.c = c;
 ​
  return y;
 };

 P.round = function (dp, rm) {
  if (dp === UNDEFINED) dp = 0;
  else if (dp !== ~~dp || dp < -MAX_DP || dp > MAX_DP) {
  throw Error(INVALID_DP);
  }
  return round(new this.constructor(this), dp + this.e + 1, rm);
 };
 ​
 function round(x, sd, rm, more) {
  var xc = x.c;
 ​
  if (rm === UNDEFINED) rm = Big.RM;
  if (rm !== 0 && rm !== 1 && rm !== 2 && rm !== 3) {
  throw Error(INVALID_RM);
  }
 ​
  if (sd < 1) {
  // 兜底情况,精度小于1,默认有效值为1
  more =
  rm === 3 && (more || !!xc[0]) || sd === 0 && (
  rm === 1 && xc[0] >= 5 ||
  rm === 2 && (xc[0] > 5 || xc[0] === 5 && (more || xc[1] !== UNDEFINED))
  );
 ​
  xc.length = 1;
 ​
  if (more) {
 ​
  // 1, 0.1, 0.01, 0.001, 0.0001 等等
  x.e = x.e - sd + 1;
  xc[0] = 1;
  } else {
  // 定义为0
  xc[0] = x.e = 0;
  }
  } else if (sd < xc.length) {
 ​
  // xc数组中,在精度之后的纸会被舍弃取整
  more =
  rm === 1 && xc[sd] >= 5 ||
  rm === 2 && (xc[sd] > 5 || xc[sd] === 5 &&
  (more || xc[sd + 1] !== UNDEFINED || xc[sd - 1] & 1)) ||
  rm === 3 && (more || !!xc[0]);
 ​
  // 删除所需精度后的数组值
  xc.length = sd--;
 ​
  // 取整方式判断
  if (more) {
 ​
  // 四舍五入可能意味着前一个数字必须四舍五入,所以这个时候需要填0
  for (; ++xc[sd] > 9;) {
  xc[sd] = 0;
  if (!sd--) {
  ++x.e;
  xc.unshift(1);
  }
  }
  }
 ​
  // 删除小数点后面的0
  for (sd = xc.length; !xc[--sd];) xc.pop();
  }
 ​
  return x;
 }

如果大家希望看有中文注释的代码,也可以去我的GitHub中看我folk的代码,里面有部分中文,后续也会补齐。

如果大家后续需要对大数进行操作,可以考虑使用这个精简又方便的库。

总体上来说,我还是推荐大家使用像big.js这种库对大数进行处理,一个是能够保证各平台兼容性,不存在跨平台和容器高低版本问题,另一个是数字数据类型统一,方便后续统一处理(BigInt和Number类型不可一起运算,BigInt不支持Math对象中的方法)。

在最新的JavaScript中,也支持了大整型的数据类型——BigInt。这个能够覆盖在整型数字超过Number类型时的一些运算和处理,有兴趣的同学也可以去看看。

总体上来说,big.js是一个非常精简的库。它的源码还是比较便于理解的。这个方式比之前的long.js来说,操作更加的简单,看上去也更加的通俗易懂。

总结

但是,在代码中,其实我们也发现了一些小的瑕疵,比如常量定义使用的数字,而不是更加便于理解的常量或者字符串,这个其实是可以再进行优化的。

  • 大数的处理方式。通过源码阅读能够使我们更加明确数字的运算方法。
  • 处理顺序统一。在每一个运算函数中,我们都是先进行异常检测,然后对数据进行处理,最终,我们定义了统一的处理逻辑,对数据进行运算操作。如果遇到不符合这种处理逻辑的数值,我们都在处理前被转化成了符合要求的值。这样,我们的代码看起来条理清晰,思路明确,不需要通过不同的逻辑处理代码来处理不同类型的数据。

我们来看下在源码中,有哪些优秀的地方值得我们学习:

还有一些我们没有提到过的运算操作,例如取绝对值、减法、除法、次方等,原理都很简单。他们都是通过操作我们存储在实例中的三个属性:符号、小数点位和数字的字符串,来获取最终的结果。这个由于篇幅原因,我们就不过多赘述了,大家有兴趣的可以去看看源码。

在big.js的源码中,我们看到了大数的处理方式——通过将大数拆解成每一位,然后进行每一位运算,得到结果。

源码解析小结

在正常的逻辑中,我们根据精度舍弃了精度后的值,统一填充0进行表示。

通过内部的round函数的实现可以看到,在最开始我们进行了异常的兜底检测,排除了两种异常的情况。一种是参数错误,直接抛出异常;另一种是精度小于1的情况,在这个时候,定义了兜底的值1。

在big.js中,所有的取整运算都调用了内部的一个round函数。那么,接下来,我们就以API中的round方法为例。这个方法有两个参数,第一个值dp代表着小数后有效值的位数,第二个rm代表了取整的方式。

看完了四则运算中有代表的加法和乘法,我们来看下取整这个运算。

取整

乘法的整体思路也是类似,先确定符号,然后调整小数点位数,最后进行乘法运算得到最终的结果。整体的代码看上去还是很清晰。

看完了简单的加法,我们来看下稍微复杂一些的乘法。其实乘法的本质和加法也是类似的,每一位数字进行运算后再保存回原数组即可。想想我们小学学过的乘法计算方式,那么就不难理解这个代码。

乘法

在代码中,big.js通过一些边界条件判断和交换的方法,保证了运算流程的简单。

通过上述的代码中,我们可以看到,加法操作其实就是在符号相同的情况下,对齐两个数字的小数点,然后对数组中的每一对数据进行加法操作,得到结果后再保存下来。这个算是一个比较简单的操作。

首先我们来看下四则运算中最简单的加法,这个我们简单思考下就很简单了,只需要判断下符号,对应上位数进行加减运算即可。我们看下具体的实现代码。

加法

因为big.js支持的运算比较多,因此我们就选几个比较有代表性的,其他的大家感兴趣,可以自己顺着源码看下,整体上还是很好理解的。

API源码解析

通过上述的存储结构描述,大家应该对big.js的数据存储方式有了一个清楚的了解。大家应该也能够大概猜到,接下来的一些运算函数,应该如何对这些数据进行操作了。接下来,我们挑选几个最常见的函数,验证下我们的想法是不是准确的。

  • s,表示符号,-1表示负数,1表示正数。
  • c,是一个数组,存储了当前数字的每一位的值。
  • e,表示小数的开始位数,即在数组中的第几个元素是小数的开始。比如[1,2,3,4]中,如果e是2,那么就代表着12.34。

通过parse函数,我们就已经把构造函数传入的数据转化成了Big类的实例中的属性了。其中,Big类实例中的变量,存储的值对应的含义如下:

parse函数中,进行了数据的解析处理。首先,我们判断了是否符合数字的标准,如果符合的话,我们对传入的数据表示的数字方法进行了判断,是不是负数、是不是小数、有没有适用科学计数法,同时对一些无意义的0进行了处理。

在构造函数中,传入的变量n经过各种类型判断,最终变成了一个字符串,传给了parse函数。那么,我们接下来看看parse函数做了什么。

我们首先来看下构造函数。

变量存储

常量定义我们就不过多介绍了,这个代码没有什么复杂的。我们主要来看下内部的数据在初始化后如何进行存储的,以及我们选择几个特定的API,看下这些API是如何实现的。

big.js的源码内容比较少,都在big.js一个文件中,大家如果想要阅读,直接看这个文件就行。接下来让我们来看一下big.js的代码结构。

源码解析

  • abs,取绝对值。
  • cmp,compare的缩写,即比较函数。
  • div,除法。
  • eq,equal的缩写,即相等比较。
  • gt,大于。
  • gte,小于等于,e表示equal。
  • lt,小于。
  • lte,小于等于,e表示equal。
  • minus,减法。
  • mod,取余。
  • plus,加法。
  • pow,次方。
  • prec,按精度舍入,参数表示整体位数。
  • round,按精度舍入,参数表示小数点后位数。
  • sqrt,开方。
  • times,乘法。
  • toExponential,转化为科学计数法,参数代表精度位数。
  • toFied,补全位数,参数代表小数点后位数。
  • toJSON和toString,转化为字符串。
  • toPrecision,按指定有效位数展示,参数为有效位数。
  • toNumber,转化为JavaScript中number类型。
  • valueOf,包含负号(如果为负数或者-0)的字符串。

运算符操作函数

  • DP,小数点后位数,默认值是20
  • RM,四舍五入方式,默认为1,代表向最近的整数取整。如果是0.5,那么向下取整。
  • NE:在转换为字符串时展示为科学计数法的最小小数位数。默认值是-7,即小数点后第7为才开始不是0。
  • PE:在转换为字符串时展示位科学计数法的最小整数位数。默认值是21,即数字长度超过21位。
  • strict:默认值为false。设置为true时,构造函数只接受字符串和大数。

big.js的常量定义一共有5个,分别的含义是:

常量定义

接下来,我们一个一个部分来看。

  • 常量定义
  • 运算操作函数

big.js的API主要分为以下两个部分:

API简介

如果想要了解big.js具体支持哪些方法,可以阅读big.js API文档

通过代码,我们可以看到,big.js所有的操作都是基于Big类的。Big类实现了我们在数字运算中的一些常见的操作,例如加减乘除、比较等。基本上你用到的操作,应该都是支持了。

查看原文

赞 0 收藏 0 评论 0

hjava 发布了文章 · 2020-11-29

正则表达式是如何让你的网页卡住的

概述

正则表达式在我们日程的工作项目中,应该是一个经常用到的技能。在做一些字符的匹配和处理的过程中,发挥了很大的作用。我们这篇文章主要是通过一个我在工作中遇到的性能问题,来探究下正则表达式是如何影响我们的代码性能的。在我们遇到了正则表达式有性能平静的时候,我们应该如何的来对它进行优化?

如果对正则表达式还没有什么概念,或者说不了解的同学,可以先参考我之前写过的博客:

问题现状

在我们日常的工作中,如果不需要去调整正则表达式的话,大部分人其实是会选择性忽略它的。这就导致了大部分人对正则表达式其实并不是太了解。在正则表达式出现问题以后也不知道如何去解决。

因为我在美团是负责做大象Web/PC的相关开发,所以在日常的工作中免不了要经常和正则表达式打交道,比如识别文本消息中的URL进行高亮,或者说识别会议室、解析特定格式展示不同的UI等。在这种情况下,我免不了会跟大量的正则表达式打交道。从长时间与正则打交道的经历中,也有了部分的经验总结。

下面我们通过一个工作中具体的例子,来看下正则表达式是如何让你的网页卡住的?

在最近的性能问题优化排查中,我们发现在遇到文字内容较多(约15000字)的文本消息文字处理时,render函数会有一个比较大的性能损耗,每次渲染需要差不多100ms。因为消息每次渲染都是20条一起,因此正则表达式一旦有性能问题,就会因为多次渲染的放大效应,被用户很明显的感知到。如果每条消息处理都需要100ms,那么20条消息处理就会直接卡顿2s,这其实对于用户来说是不可以接受的。

具体我们可以看下火焰图(火焰图就是Chrome的devtools中,分析profile时候的图表,大家可以理解为一个调用时间图谱,如果不了解,推荐看看阮一峰老师的如何读懂火焰图? - 阮一峰的网络日志):
image.png

通过上述的火焰图,我们可以看到这个render渲染函数每次执行都差不多100ms。对于JavaScript来说,100ms其实时间已经很长了。那么这一百毫秒中具体干了哪些事情呢?

我们简单的梳理一下当前的代码,发现最有可能的原因就是正则耗时的影响。在消息处理中,有两个需要进行匹配的正则,一个是匹配会议室进行高亮的,一个是匹配引用消息进行格式转换的。这两个正则分别如下:

const QUOTED_MSG_REG = /([^「]*?)「((?:[a-zA-Z0-9\u4E00-\u9FBF_\.\s]{0,40})\:(?:.|\n)*)」\n(—){10}\n((?:\S|\s)*)$/m;

const MEETING_ROOM_REG = /北京厅|天津厅|石家庄厅|济南厅|哈尔滨厅|...(此处省略200+个会议室)|台湾厅/mg;

这个两个正则表达式用来匹配的文本如下:

// 引用格式
「张三:老司机」
——————————
带带我

// 会议室
张三呀,我们去 常德厅 开个会吧,叫上其他人

一开始看,大家可能觉得这两个正则都很正常,我们在正常的工作中也会写出这样的正则表达式,没有发现什么问题。

如果告诉你这两个正则表达式执行有性能问题,那么大家可能还会觉得,会议室匹配的文本正则这么长,需要匹配的会议室这么多,肯定是这个正则有性能问题,导致了执行时间过长。

那么具体情况到底是不是和我们直观感受一样呢?我们来对具体问题进行一个分析。

问题分析

为了分析我们上面说到的这两个正则表达式性能到底怎么样,我从网上找了一些文字,来模拟消息的内容。通过使用正则表达式进行匹配,在Node端执行计算耗时,得到的一个字数与时间的关系图如下,表格的横坐标是字数,纵坐标是时间(ms):
image.png

这个和大家的猜测是不是一样?在我之前最早的猜测中,我也以为是正则长度越长,那么性能就越差。但是,这个和我的猜测正好相反,反倒是看上去比较短的。引用正在表达式性能问题最大。

从我们分析的数据来看,在10000字之前,其实差别没有那么大。 但是在超过10,000个字的时候,其实耗时差异就比较明显了。

大家可以看到引用的这个正则表达式,他的耗时其实是发生了指数型的上升。 在超过50,000字,以后其实这个正则你可以认为基本上就不能够再使用了,而且这还是在性能比较好的MacBook情况下。 如果是在一些更老的电脑,或者说Windows的低端本上,那么这个耗时其实还会更大。你想想你,你能够接受你的开发的项目,卡住2秒不动吗?

反倒是我们觉得比较复杂的这个会议室正则表达式,它在匹配的内容字数增加的情况下,性能其实没有明显的增加,一直都稳定在100毫秒以下。

看到这里,有人可能会觉得是不是match方法,它比较吃性能呢?也有人可能会想,我们是不是在match之前增加一个相同正则表达式的test判断?如果符合的话,我们再执行match,这样是不是就能够提高我们的性能呢?

那么我们把match方法换成test方法来看一下,这样能不能够提升我们正则匹配的性能呢?下图是我们使用会议室正则表达式来进行匹配的一个耗时图。我们从图中可以看到相关的执行耗时情况:
image.png

从图中可以看到,test方法并不会比match方法节省更多的时间,相反来看他的耗时其实比match还略微有增加。不过可能就是几个毫秒。我尝试了一下性能问题更明显的引用正则表达式,得到了结论也是一样的。所以我们想到的先使用test方法来进行判断,如果test方法命中的话再进行match。这个不但没有优化,反倒是可能会损耗双倍的性能。

既然相同的正则表达式使用任意一个方法执行的时候都会有比较明显的性能问题,那么我们就只能从正则表达式本身的优化入手了。我们来看一下,为什么我们觉得比较复杂的正则表达式,耗时没有什么变化。反而我们认为比较简单的正则表达式时间的增长却这么明显呢?

原理分析

其实,正则表达式性能最大的影响来自于正则表达式的回溯。如果一个正则表达式回溯的越多,那么它的性能损耗就越明显。我们可以去看一下上面两个正则表达式的情况。

其实上面两个正则表达式都有回溯的问题。如果大家不了解,回溯,可以去看下我之前的那一篇 正则表达式高级进阶。在这里我们简单介绍一下回溯回溯的原因:正则表达式在匹配的过程中需要往回走重新进行匹配,这就会导致回溯。一般产生回溯的有这么几种情况,一种是分支,一种是量词。

我们可以看看上面两个正则表达式,会议是这个正则比较简单,他其实是很多分支的集合体;引用的这个正则就不同了,他的回溯主要是来源于量词。尤其是[^「]*这种的存在,导致了大量的回溯情况。

所以说一个正则表达式性能好不好跟他的长短没有必然的联系。而是跟他具体的写法有关。如果这个正则表达式很多地方都有回溯的情况,那么他的性能必然就好不了。反过来说,如果一个正则表达式虽然很长很复杂,但是它能够尽可能的避免回溯。需要匹配的文本也尽可能的清晰,那么这种情况下它的性能其实是很不错的。

解决方案

遇到这个问题,我们一般会有以下两个解决方案。

优化正则表达式本身

第一个解决方案就是尽可能的去优化这个正则表达式本身,去尽可能消除里面一些回溯的情况。这个也是我们一般最常用的一个解决方案。具体有以下2个操作:

  1. 在明确匹配规则的情况下,使用\d{1, 30}来替换.*,尽可能的去明确我们需要匹配的类型与长度。
  2. 在需要进行不明确数量匹配的时候,尽可能的使用非贪婪匹配,而不是使用贪婪匹配。

同时,还有个规则:在不需要捕获组的情况下,括号尽可能的使用非捕获组(与回溯无)。

总体上来说就是:如果一个正则表达式越精确,捕获的元素越少,那么它的性能就会越好。反之,如果有大量的模糊匹配跟回溯的情况,那么它的性能大概率就不怎么好。

在一般的场景中,我们使用了这个方法,基本上我们的性能问题就能够迎刃而解了。

但是,那么如果我们继续要匹配比较复杂的正则,同时这个正则又没有办法避免回溯的情况,我们应该怎么去优化这个性能的?

优化正则表达式匹配顺序

也就是说在这种情况下,这个正则表达式其实是没有办法再进行优化了,但是我们又需要在日常的项目中使用,不能直接废弃。这就需要我们使用另外的优化方案了。

在正则没有办法修改的情况下,我们可以做正则匹配的分级,尽可能使用一些性能比较高的正则表达式,先进行一些过滤匹配。在命中我们需要匹配的条件以后,再使用比较复杂的正则表达式进行匹配。从而避免复杂的正则表达式频繁的被调用。

我举一个简单的例子,还是以上面的引用正则表达式来分析。如果这个正则表达式我没有办法再进行进一步优化了情况下,我们可以先把他的一些特定的规则摘取出来,进行一个前置校验。我们可以简单的来看一下下面一个代码示例:

let str = 'xxxxxx'; //长文本

const LINE_REG = /\n(—){10}\n/m;
const QUOTED_MSG_REG = /([^「]*?)「((?:[a-zA-Z0-9\u4E00-\u9FBF_\.\s]{0,40})\:(?:.|\n)*)」\n(—){10}\n((?:\S|\s)*)$/m;

if(LINE_GER.test(str)) {
    let result = str.match(QUOTED_MSG_REG);
    // do something
}

不要在主线程中执行

如果一个正则表达式没有办法通过上述两种方案进行优化(这个概率其实已经很低了,感觉和彩票中奖差不多了),那么我们还有一个最终的解决方案,就是使用Web Workder,来进行耗时的操作计算。

这样的话,我们至少在主线程执行过程中,不会有卡住影响用户操作的问题。

不过,在这个方案中,需要考虑到大量数据通过postMessage传递到Web Worker中的性能损耗问题。

这个方案本质上比较简单,我在具体项目中也没有使用到,因此不展开讲了,有兴趣了解的同学可以自行上网查阅相关资料,或者评论私信留言讨论。

从上面的代码中我们可以看到,我们可以选取一个没有回溯的明确特征条件来先进行一次快速的匹配。一般情况来说没有回溯的正则匹配效率都是特别高,即使是在大量文本处理的情况下也不会对性能有什么太大的影响。在进行了第一次正则表达式匹配后,如果这个文本还是符合当前的条件,那么说明有较大概率它其实是需要我们命中的,那么我们再执行正则匹配即可。

这样的话,我们就能够避免大部分的无意义的性能消耗。

服务端数据处理

如果一个数据量太过庞大(超过1M的文本)时,我推荐对数据进行分页,不要一次性处理所有数据(这个时候正则已经不是瓶颈了,JS执行引擎才是瓶颈)。

但是,有些神奇的项目就是会有这种诉求,遇到这种情况时,我们必须(不是可以,是必须)借助服务端来进行数据处理,前端只做简单的展示逻辑(即使是展示这么大量的数据,渲染也会有比较明显的卡顿和耗时)。

如果没有后端的支持,那么自己用Node搭建一个简单的中转处理服务都行。这个时候需要关注的,就是自己的Node服务如何能够弹性扩容了。

效果验证

在我的项目遇到的性能问题中,只使用了前两个方案对引用的正则表达式进行了优化。我们可以来看一下优化后的渲染耗时情况:
image.png

在通过对正则表达式进行优化后,我们的每次文本渲染时间从100ms直接降到了不到2ms。 这可是50倍的性能提升。对于15000字的文本来说,这个速度可以算是没有任何的性能影响了。

我们还试了试极限情况下1000000字的情况,渲染也能够控制在20ms以内,这和之前相比,进步还是很明显的。

总结

正则表达式在我们的日常代码使用中其是很常见的。但是稍有不慎我们就会遇到性能问题。大部分在写代码的过程中,不会去考虑这个正则表达式性能怎么样,都会下意识觉得反正处理的文本长度不大,写的再差也没有什么影响。但是,在项目逐渐发展过程中,有可能由于产品策略调整或者数据的积累,某一个不起眼的正则表达式,就会对整个项目的性能产生决定性影响。

因此我们在具体开发的过程中一定要有性能的意识,我们写的任意一个正则表达式都有可能会导致整个系统的性能问题。因此我们写的每一个正则表达式都应该尽可能的准确,尽可能的减少执行次数。

再遇到正则的性能问题时,正则表达式的优化手段主要有3个:

  1. 我们需要尽可能的去让我们的正则表达式准确化,越准确的正则表达式匹配时,他的回溯情况就越少,所以它的性能就越高。
  2. 在正则表达式已经没有办法再进行优化的情况下,我们可以先选取一些没有回复情况的特征值进行先置条件判断,这样的话,我们能够尽量多的去避免一些无意义的好事匹配,优化我们的性能。
  3. 借助其他线程或者服务来进行正则处理,避免用户卡顿。

希望能够通过上述的具体实战优化,能够让大家了解正则表达式在项目中对性能的影响,也欢迎大家在遇到正则表达式相关的问题时,随时讨论交流,大家一起解决问题,一起进步。

查看原文

赞 16 收藏 13 评论 0

hjava 赞了文章 · 2020-11-20

EventEmitter源码浅析

EventEmitter3是个啥

EventEmitter3是高性能的EventEmitter。

源码浅析

废话不多说,直接进入正题~~
下面我们来看一下它的源码
首先看一下EventEmitter3的大致结构
image.png
EventEmitter类有两个私有属性,_events和_eventCounts,_events是Events的是一个实例,_eventCounts是为后面移除事件判断的一个参数,EventEmitter原型上的方法如上图中所示,Events就是一个普通的类对象;
下面一一看下EventEmitter原型上的方法是如何实现的

  • eventNames
EventEmitter.prototype.eventNames = function eventNames() {
  var names = []
    , events
    , name;

  if (this._eventsCount === 0) return names;

  for (name in (events = this._events)) {
    if (has.call(events, name)) names.push(prefix ? name.slice(1) : name);
  }

  if (Object.getOwnPropertySymbols) {
    return names.concat(Object.getOwnPropertySymbols(events));
  }

  return names;
};

eventNames 返回当前已经注册的事件名称的列表;
在实现eventNames的时候有用到prefix,看下设置prefix的代码

var prefix = '~';
if (Object.create) {
  Events.prototype = Object.create(null);
  if (!new Events().__proto__) prefix = false;
}
  • listeners
EventEmitter.prototype.listeners = function listeners(event) {
  var evt = prefix ? prefix + event : event
    , handlers = this._events[evt];

  if (!handlers) return [];
  if (handlers.fn) return [handlers.fn];

  for (var i = 0, l = handlers.length, ee = new Array(l); i < l; i++) {
    ee[i] = handlers[i].fn;
  }

  return ee;
};

返回某一个事件名称的所有监听函数

  • listenerCount
EventEmitter.prototype.listenerCount = function listenerCount(event) {
  var evt = prefix ? prefix + event : event
    , listeners = this._events[evt];

  if (!listeners) return 0;
  if (listeners.fn) return 1;
  return listeners.length;
};

返回某一个事件名称的所有监听函数的length

  • emit
EventEmitter.prototype.emit = function emit(event, a1, a2, a3, a4, a5) {
  var evt = prefix ? prefix + event : event;

  if (!this._events[evt]) return false;

  var listeners = this._events[evt]
    , len = arguments.length
    , args
    , i;

  if (listeners.fn) {
    if (listeners.once) this.removeListener(event, listeners.fn, undefined, true);

    switch (len) {
      case 1: return listeners.fn.call(listeners.context), true;
      case 2: return listeners.fn.call(listeners.context, a1), true;
      case 3: return listeners.fn.call(listeners.context, a1, a2), true;
      case 4: return listeners.fn.call(listeners.context, a1, a2, a3), true;
      case 5: return listeners.fn.call(listeners.context, a1, a2, a3, a4), true;
      case 6: return listeners.fn.call(listeners.context, a1, a2, a3, a4, a5), true;
    }

    for (i = 1, args = new Array(len -1); i < len; i++) {
      args[i - 1] = arguments[i];
    }

    listeners.fn.apply(listeners.context, args);
  } else {
    var length = listeners.length
      , j;

    for (i = 0; i < length; i++) {
      if (listeners[i].once) this.removeListener(event, listeners[i].fn, undefined, true);

      switch (len) {
        case 1: listeners[i].fn.call(listeners[i].context); break;
        case 2: listeners[i].fn.call(listeners[i].context, a1); break;
        case 3: listeners[i].fn.call(listeners[i].context, a1, a2); break;
        case 4: listeners[i].fn.call(listeners[i].context, a1, a2, a3); break;
        default:
          if (!args) for (j = 1, args = new Array(len -1); j < len; j++) {
            args[j - 1] = arguments[j];
          }

          listeners[i].fn.apply(listeners[i].context, args);
      }
    }
  }

  return true;
};

用来触发某个事件

  • on
EventEmitter.prototype.on = function on(event, fn, context) {
  return addListener(this, event, fn, context, false);
};

用来注册某个事件

  • once
EventEmitter.prototype.once = function once(event, fn, context) {
  return addListener(this, event, fn, context, true);
};

和on差不多,只是once只会触发一次

  • removeListener
EventEmitter.prototype.removeListener = function removeListener(event, fn, context, once) {
  var evt = prefix ? prefix + event : event;

  if (!this._events[evt]) return this;
  if (!fn) {
    clearEvent(this, evt);
    return this;
  }

  var listeners = this._events[evt];

  if (listeners.fn) {
    if (
      listeners.fn === fn &&
      (!once || listeners.once) &&
      (!context || listeners.context === context)
    ) {
      clearEvent(this, evt);
    }
  } else {
    for (var i = 0, events = [], length = listeners.length; i < length; i++) {
      if (
        listeners[i].fn !== fn ||
        (once && !listeners[i].once) ||
        (context && listeners[i].context !== context)
      ) {
        events.push(listeners[i]);
      }
    }

    //
    // 重置数组,如果没有其他侦听器,则将其完全删除.
    //
    if (events.length) this._events[evt] = events.length === 1 ? events[0] : events;
    else clearEvent(this, evt);
  }

  return this;
};

移除某个事件的监听函数

  • removeAllListeners
EventEmitter.prototype.removeAllListeners = function removeAllListeners(event) {
  var evt;

  if (event) {
    evt = prefix ? prefix + event : event;
    if (this._events[evt]) clearEvent(this, evt);
  } else {
    this._events = new Events();
    this._eventsCount = 0;
  }

  return this;
};

移除某个事件的所有监听函数

总结

代码量较少,但也有一些缺点吧,就是有较多的重复代码,没有进行抽象整理代码,但是EventEmitter在做类库或者框架的时候就很有用了,因为它把事件和事件的处理解耦,事件的触发者不必关心事件是由谁来处理,怎么处理的;整体来说,EventEmitter结构简单,还是很友好的!

查看原文

赞 1 收藏 0 评论 0

hjava 赞了文章 · 2020-11-20

EventEmitter3 初探

一、什么是EventEmitter?

EventEmitter(事件派发器)是一个对事件进行监听的对象,简单来说就是为事件写回调函数,当触发一个事件执行后,会执行为该事件绑定的回调函数。

JavaScript 事件最核心的包括事件监听 (addListener)、事件触发 (emit)、事件删除 (removeListener),理解如下:
image.png
考虑一个DOM事件:

// Typescript
const button = document.querySelector('button');
button.addEventListener("click", (event) => {
    // do something with the event
})

我们向按钮单击事件添加了一个listener (监听器),并且已经订阅了一个正在被发出的事件,当事件发生时会触发回调。每次单击该按钮时,都会发出该事件,而该事件会触发回调。

当处理现有代码库时,或许需要触发自定义事件。不像单击按钮这样的特定DOM事件,而是假设想基于其他触发器发出一个事件,并得到一个事件响应。我们需要一个自定义事件派发器来实现这一点。

事件派发器是一种模式,它监听一个已命名的事件,触发回调,然后发出该事件并附带一个值。有时这被称为“发布/订阅”模型或监听器。它们指的是同一件事。

二、相关知识

Symbol属性


Symbol是ES6中的添加了一种原始数据类型symbol(已有的原始数据类型:String, Number, boolean, null, undefined, 对象),由于每一个Symbol值都是不相等的,这意味着Symbol值可以作为标识符,用于对象的属性名,就会保证不会出现同名的属性。

这对于一个对象由多个模块构成的情况非常有用,能防止某一个键被不小心改写或者覆盖。

用法举例:

let mySymbol = Symbol();
 
// 第一种写法
let a = {};
a[mySymbol] = 'Hello!';
 
// 第二种写法
let a = {
  [mySymbol]: 'Hello!'
};
 
// 第三种写法
let a = {};
Object.defineProperty(a, mySymbol, { value: 'Hello!' });
 
// 以上写法都得到同样结果
a[mySymbol] // "Hello!"

Object.getOwnPropertySymbols


Object.getOwnPropertySymbols()方法返回一个数组,包含给定对象所有自有的Symbol值的属性(包括不可枚举的Symbol值属性)。
语法

Object.getOwnPropertySymbols(obj); 
// 参数 obj:要获取自有Symbol值属性的对象;返回值一个包含给定对象所有自有的Symbol值的属性的数组。

所有的对象在初始化时都不会包含任何的Symbol值属性,除非在对象上显式定义了Symbol值属性,否则该方法会返回一个空数组。

例:获取对象自有的Symbol值属性

var a = Symbol('a');
var b = Symbol('b');
var obj = {};
obj[a] = 1;
obj[b] = 2;
Object.getOwnPropertySymbols(obj); // [Symbol(a), Symbol(b)]

var c = Symbol('c');
Object.defineProperty(obj, c, {
    value: 3,
    enumerate: false,
    writable: false,
    configuration: false
});
Object.getOwnPropertySymbols(obj); // [Symbol(a), Symbol(b), Symbol(c)]

三、源码分析

EventEmitter3是一个典型的第三方事件库,能够让我们自定义实现多个函数与组件间的通信。

1、项目主要内容


本项目的结构比较清晰,主要包括的内容是:

  • 表示单个事件侦听器的EE
  • Prototype属性:保存事件与监听器的_events属性
  • 方法的定义

    1. 为给定事件添加侦听器的addListener方法
    2. 按名称清除事件的clearEvent方法
    3. 与Node.js EventEmitter接口兼容的最小的EventEmitter接口
  • EventEmitter.prototype上的方法定义

    1. eventNames方法:该方法返回一个数组,该数组包含发射器emitter已为其注册侦听器的事件
    2. listeners方法:返回为给定事件注册的侦听器
    3. listenerCount:返回侦听给定事件的侦听器数
    4. emit:调用为给定事件注册的每个侦听器
    5. on:为给定事件添加侦听器
    6. once:为给定事件添加一次性侦听器
    7. removeListener:移除给定事件的侦听器
    8. removeAllListeners:删除所有侦听器或指定事件的侦听器
  • 为removeListener和on方法别名
  • prefix和EventEmitter导出

2、内容详解


下面对内容进行具体讲解

/**
 * Representation of a single event listener.
 *
 * @param {Function} fn The listener function.
 * @param {*} context The context to invoke the listener with.
 * @param {Boolean} [once=false] Specify if the listener is a one-time listener.
 * @constructor
 * @private
 */
function EE(fn, context, once) {
  this.fn = fn;
  this.context = context;
  this.once = once || false;
}

EE:

  • 这个EventEmitter类保存了监听器方法、上下文和该监听器是否为一次性监听器的once标志(默认不是一次性监听器)
/**
 * Add a listener for a given event.
 *
 * @param {EventEmitter} emitter Reference to the `EventEmitter` instance.
 * @param {(String|Symbol)} event The event name.
 * @param {Function} fn The listener function.
 * @param {*} context The context to invoke the listener with.
 * @param {Boolean} once Specify if the listener is a one-time listener.
 * @returns {EventEmitter}
 * @private
 */
function addListener(emitter, event, fn, context, once) {
  if (typeof fn !== 'function') {
    throw new TypeError('The listener must be a function');
  }

  var listener = new EE(fn, context || emitter, once)
    , evt = prefix ? prefix + event : event;

  if (!emitter._events[evt]) emitter._events[evt] = listener, emitter._eventsCount++;
  else if (!emitter._events[evt].fn) emitter._events[evt].push(listener);
  else emitter._events[evt] = [emitter._events[evt], listener];

  return emitter;
}

addListener:

  • 通过调用EE类的new方法生成一个listener实例,判断Object.create()方法是否存在,存在则使用该方法创建属性,否则通过为事件增加前缀避免属性覆盖
  • 判断发射器的_events的evt属性,如果该属性为undefined,直接给evt事件注册listener监听器,并增加事件个数
  • 如果发射器_events的evt属性是一个对象,并且已经存在事件监听器,使用push方法将listener注册成为evt事件的监听器
  • 如果发射器上存在给定的事件,事件存在一个与Listener不相等的监听器对象,将evt的监听器转化为包含这两个监听器的数组
/**
 * Clear event by name.
 *
 * @param {EventEmitter} emitter Reference to the `EventEmitter` instance.
 * @param {(String|Symbol)} evt The Event name.
 * @private
 */
function clearEvent(emitter, evt) {
  if (--emitter._eventsCount === 0) emitter._events = new Events();
  else delete emitter._events[evt];
}

clearEvent:

  • 当发射器只有一个事件时,将事件数量设置为0,且重新生成一个事件
  • 否则直接从发射器删除该事件
/**
 * Minimal `EventEmitter` interface that is molded against the Node.js
 * `EventEmitter` interface.
 *
 * @constructor
 * @public
 */
function EventEmitter() {
  this._events = new Events();
  this._eventsCount = 0;
}

EventEmitter:

  • 定义与Node.js EventEmitter接口兼容的最小的EventEmitter接口,包含存储事件的内存空间和事件数量
/**
 * Return an array listing the events for which the emitter has registered
 * listeners.
 *
 * @returns {Array}
 * @public
 */
EventEmitter.prototype.eventNames = function eventNames() {
  var names = []
    , events
    , name;

  if (this._eventsCount === 0) return names;

  for (name in (events = this._events)) {
    if (has.call(events, name)) names.push(prefix ? name.slice(1) : name);
  }

  // Object.getOwnPropertySymbols()方法返回一个数组,包含给定对象所有自有的Symbol值的属性(包括不可枚举的Symbol值属性)
  if (Object.getOwnPropertySymbols) {
    return names.concat(Object.getOwnPropertySymbols(events));
  }

  return names;
};

EventEmitter.prototype.eventNames:

  • 事件数量为0时返回空数组
  • 否则返回发射器的_events属性中的事件(去除增加的prefix前缀)和_events属性上的Symbol属性事件
/**
 * Return the listeners registered for a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @returns {Array} The registered listeners.
 * @public
 */
EventEmitter.prototype.listeners = function listeners(event) {
  var evt = prefix ? prefix + event : event
    , handlers = this._events[evt];

  if (!handlers) return [];
  if (handlers.fn) return [handlers.fn];

  for (var i = 0, l = handlers.length, ee = new Array(l); i < l; i++) {
    ee[i] = handlers[i].fn;
  }

  return ee;
};

EventEmitter.prototype.listeners:

  • 如果发射器上没有事件,返回空数组
  • 如果事件上只注册了一个监听器,直接返回包含该监听器的数组
  • 如果事件上注册了多个监听器,遍历存储所有监听器并返回
/**
 * Return the number of listeners listening to a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @returns {Number} The number of listeners.
 * @public
 */
EventEmitter.prototype.listenerCount = function listenerCount(event) {
  var evt = prefix ? prefix + event : event
    , listeners = this._events[evt];

  if (!listeners) return 0;
  if (listeners.fn) return 1;
  return listeners.length;
};

EventEmitter.prototype.listenerCount:

  • 事件没有注册监听器时返回0,只有一个监听器时返回1,否则返回监听器数组的长度
/**
 * Calls each of the listeners registered for a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @returns {Boolean} `true` if the event had listeners, else `false`.
 * @public
 */
EventEmitter.prototype.emit = function emit(event, a1, a2, a3, a4, a5) {
  var evt = prefix ? prefix + event : event;

  if (!this._events[evt]) return false;

  var listeners = this._events[evt]
    , len = arguments.length
    , args
    , i;

  if (listeners.fn) {
    if (listeners.once) this.removeListener(event, listeners.fn, undefined, true);

    switch (len) {
      case 1: return listeners.fn.call(listeners.context), true;
      case 2: return listeners.fn.call(listeners.context, a1), true;
      case 3: return listeners.fn.call(listeners.context, a1, a2), true;
      case 4: return listeners.fn.call(listeners.context, a1, a2, a3), true;
      case 5: return listeners.fn.call(listeners.context, a1, a2, a3, a4), true;
      case 6: return listeners.fn.call(listeners.context, a1, a2, a3, a4, a5), true;
    }

    for (i = 1, args = new Array(len -1); i < len; i++) {
      args[i - 1] = arguments[i];
    }

    listeners.fn.apply(listeners.context, args);
  } else {
    var length = listeners.length
      , j;

    for (i = 0; i < length; i++) {
      if (listeners[i].once) this.removeListener(event, listeners[i].fn, undefined, true);

      switch (len) {
        case 1: listeners[i].fn.call(listeners[i].context); break;
        case 2: listeners[i].fn.call(listeners[i].context, a1); break;
        case 3: listeners[i].fn.call(listeners[i].context, a1, a2); break;
        case 4: listeners[i].fn.call(listeners[i].context, a1, a2, a3); break;
        default:
          if (!args) for (j = 1, args = new Array(len -1); j < len; j++) {
            args[j - 1] = arguments[j];
          }

          listeners[i].fn.apply(listeners[i].context, args);
      }
    }
  }

  return true;
};

EventEmitter.prototype.emit:

  • 当触发给定事件时,只需要调用emit方法。该方法会自动检索事件event中所有的事件监听器,触发所有的事件监听函数,同时移除掉通过once添加的一次性监听器
/**
 * Add a listener for a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @param {Function} fn The listener function.
 * @param {*} [context=this] The context to invoke the listener with.
 * @returns {EventEmitter} `this`.
 * @public
 */
EventEmitter.prototype.on = function on(event, fn, context) {
  return addListener(this, event, fn, context, false);
};

EventEmitter.prototype.on:

  • 通过调用addListener方法为指定的事件指定上下文并注册监听器
/**
 * Add a one-time listener for a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @param {Function} fn The listener function.
 * @param {*} [context=this] The context to invoke the listener with.
 * @returns {EventEmitter} `this`.
 * @public
 */
EventEmitter.prototype.once = function once(event, fn, context) {
  return addListener(this, event, fn, context, true);
};

EventEmitter.prototype.once:

  • 通过调用addListener方法为指定的事件指定上下文并注册监听器,且通过设置once属性值为true将该监听器指定为一次性监听器
/**
 * Remove the listeners of a given event.
 *
 * @param {(String|Symbol)} event The event name.
 * @param {Function} fn Only remove the listeners that match this function.
 * @param {*} context Only remove the listeners that have this context.
 * @param {Boolean} once Only remove one-time listeners.
 * @returns {EventEmitter} `this`.
 * @public
 */
EventEmitter.prototype.removeListener = function removeListener(event, fn, context, once) {
  var evt = prefix ? prefix + event : event;

  if (!this._events[evt]) return this;
  if (!fn) {
    clearEvent(this, evt);
    return this;
  }

  var listeners = this._events[evt];

  if (listeners.fn) {
    if (
      listeners.fn === fn &&
      (!once || listeners.once) &&
      (!context || listeners.context === context)
    ) {
      clearEvent(this, evt);
    }
  } else {
    for (var i = 0, events = [], length = listeners.length; i < length; i++) {
      if (
        listeners[i].fn !== fn ||
        (once && !listeners[i].once) ||
        (context && listeners[i].context !== context)
      ) {
        events.push(listeners[i]);
      }
    }

    //
    // Reset the array, or remove it completely if we have no more listeners.
    //
    if (events.length) this._events[evt] = events.length === 1 ? events[0] : events;
    else clearEvent(this, evt);
  }

  return this;
};

EventEmitter.prototype.removeListener:

  • 如果发射器上不存在该事件,直接返回发射器
  • 事件只存在一个监听器时,调用clearEvent方法删除该监听器
  • 否则使用一个event属性来保存不需要被移除的事件监听对象,然后遍历整个事件监听器数组,并且最后将event属性的值赋值给_event属性从而覆盖掉原有的属性来删除指定的监听器
/**
 * Remove all listeners, or those of the specified event.
 *
 * @param {(String|Symbol)} [event] The event name.
 * @returns {EventEmitter} `this`.
 * @public
 */
EventEmitter.prototype.removeAllListeners = function removeAllListeners(event) {
  var evt;

  if (event) {
    evt = prefix ? prefix + event : event;
    if (this._events[evt]) clearEvent(this, evt);
  } else {
    this._events = new Events();
    this._eventsCount = 0;
  }

  return this;
};

EventEmitter.prototype.removeAllListeners:

  • 如果给定的事件存在,给该事件添加前缀,通过调用clearEvent方法将发射器上增加前缀的方法删除
  • 否则直接给发射器的_events属性指定一个Events实例并设置事件数量为0
//
// Alias methods names because people roll like that.
//
EventEmitter.prototype.off = EventEmitter.prototype.removeListener;
EventEmitter.prototype.addListener = EventEmitter.prototype.on;

别名:

  • 照顾用户习惯,方便用户使用,为EventEmitter.prototyp的removeListener和on方法别名
//
// Expose the prefix.
//
EventEmitter.prefixed = prefix;

//
// Allow `EventEmitter` to be imported as module namespace.
//
EventEmitter.EventEmitter = EventEmitter;

//
// Expose the module.
//
if ('undefined' !== typeof module) {
  module.exports = EventEmitter;
}

导出:

  • 方便用户使用导出发射器的前缀,允许用户通过import引入EventEmitter并导出EventEmitter模块

四、总结

总体来说EventEmitter3的代码比较清晰简练,代码易懂,读完能够很好地帮助了解事件的“发布/订阅”原理。

查看原文

赞 1 收藏 0 评论 0

hjava 评论了文章 · 2019-05-10

WebSocket系列之二进制数据设计与传输

概述

通过前三篇博客,我们能够了解在通过WebSocket发送数据之前,我们需要传递的数据是如何变成ArrayBuffer二进制数据的;在我们收到二进制数据之后,我们又如何将其变成了JavaScript中的常见数据类型。
本文作为WebSocket系列的第四篇内容,将会用一个简单的IM聊天应用把整个WebSocket传输二进制数据类型的内容连接起来,让用户对整个WebSocket传输二进制数据的方法有个了解。
本文的主要内容如下:

  • 如何设计一个二进制协议
  • WebSocket如何发送二进制数据
  • WebSocket如何处理接收的二进制数据

之前的博客我们介绍过了WebSocket基础知识,数字类型和字符串类型与二进制数据间的转换,如果没有相关的基础,建议先依次阅读以下文章:

如何设计一个二进制协议

什么是协议

协议,网络协议的简称,网络协议是通信计算机双方必须共同遵从的一组约定。如怎么样建立连接、怎么样互相识别等。只有遵守这个约定,计算机之间才能相互通信交流。它的三要素是:语法、语义、时序。

通过百度百科中的介绍,我们对协议的概念有了一个基础的了解。通俗来说,协议就是通信双方约定好的一套规则。

为什么要设计协议

没有规矩不成方圆。通信双方只有通过协议,才能够识别对方发送的数据内容。

我们应该如何设计这套协议

首先,协议的设计应该能够区分不同的各个数据包;其次,它还需要具备一定的兼容性。
根据上述两点要求,我们设计了一套简单的IM聊天协议,支持文本、图片、文件三种消息。这套协议是按照最简单的思路来设计的,因此也只是给大家一个参考的观点,在真正的线上使用场景中,协议会比本文中的复杂和更加有层次。具体格式如下:

{
    "id": "short", // 消息类型,1是文本协议格式;2是图片协议格式;3是文件协议格式
    "sender": "long", // 发送用户唯一id
    "reciever": "long", // 接受用户唯一id
    "data": "string" // 消息内容,如果是文本协议则为文本内容;如果是图片协议则为图片地址;如果是文件协议则为文件地址
}

这套协议如何使用

发送消息

从协议格式可知,将上述数据按照上述固定顺序放入ArrayBuffer中,即可得到一个有特定含义的二进制数据。例如:

{
    "id": 1,
    "sender": "123",
    "reciever": "456",
    "data": "Hellow World"
}

当我们需要发送此消息时,只需要:

  1. 在前2个Byte放入id
  2. 接下来8个Byte中放入sender
  3. 再接下来8个Byte放入reciever
  4. 最后紧接着放入一个string类型(以WebSocket系列之字符串如何与二进制数据进行转换博客中的格式为例,先将字符串长度构造成一个int类型,放在前4个Byte中,接下来将string类型编码后放入)。

此数据就完全按照协议构造完成了。我们只需将次协议通过WebSocket发送即可。具体方法将会在后面章节中说明。

接收消息

从协议格式可知,当我们收到一条消息时,只需要按照协议规范来进行反向解析即可。例如:

{
    "id": 1,
    "sender": "123",
    "reciever": "456",
    "data": "Hellow World"
}

如果发送端发送的数据仍然为此消息,我们的解析顺序为:

  1. 先根据前2个Byte读取一个Short类型的id数值。
  2. 将接下来的8个Byte读取为Long类型的sender字段。
  3. 再接下来的8个Byte读取为Long类型的reciever字段。
  4. 接下来读取一个string类型(以发送消息这一节的数据为例,先读取4个Byte长度的int类型字符串长度,然后再根据长度读取字符串即可)。

扩展此协议

当此协议字段无法满足并且已经在线上使用时,我们应该如何扩展呢?
根据我们的写入和读取步骤,我们可以知道:每次我们读取的二进制数据可以认为是一个格式固定的数据(string类型在构造时会有长度信息,因此认为也是长度相对固定),所以我们在读取二进制数据时读取的长度也是固定的。因此,我们在扩展时只需要往协议后面增加字段即可。

  • 扩展前的应用仍然会读取之前已经确定的数据协议,只需要保证内容不变,那么功能也不会变。
  • 扩展后的应用能够解析扩展后的协议,因此得到更多的数据,从而可以实现更多的功能。

WebSocket如何发送二进制数据

通过如何设计一个二进制协议一章,我们知道了如何定义WebSocket传输的二进制数据格式。下面,我们来看下如何在WebSocket中发送二进制数据:

let arrayBuffer = getArrayBufferMessagesFromUser(); // 获取用户需要发送的消息数据,为一个ArrayBuffer对象
let webSocket = getWebSocket(); // 获取已经连接成功的WebSocket实例

websocket.binaryType = 'arraybuffer'; // 指定WebSocket接受ArrayBuffer实例作为参数

webSocket.send(arrayBuffer);

通过上面的示例我们可以知道,WebSocket在发送string类型的数据或者ArrayBuffer类型的数据时,使用的API接口都是send方法,我们只需要在WebSocket初始化后指定传输类型binaryType即可。

WebSocket如何处理接收的二进制数据

通过WebSocket如何发送二进制数据一章,我们知道了如何发送二进制数据。接下来,让我们开看下如何处理WebSocket接收到的二进制数据:

let webSocket = getWebSocket(); // 获取已经连接成功的WebSocket实例

websocket.binaryType = 'arraybuffer'; // 指定WebSocket接受ArrayBuffer实例作为参数

webSocket.addEventListener('message', (message) => {
    let arrayBuffer = message.data; // 获取用户接收到的消息数据,为一个ArrayBuffer对象
    let data = parseMessage(arrayBuffer); // 解析二进制数据
});

通过上面的示例我们可以知道,当我们在建立连接时指定了传输类型binaryType为ArrayBuffer之后,我们通过WebSocket收到的数据也是一个ArrayBuffer实例。我们只需要根据第一章讲解的方式进行解析即可。

总结

本文作为WebSocket系列的第四篇,通过一个IM聊天应用的示例将前三篇博客分享的内容串联起来,给读者完整介绍了在WebSocket中使用二进制数据进行传输的方法以及相关的数据类型转换。
通过前面4篇博客的内容,读者可以根据自己的需求快速的构造和封装WebSocket进行二进制数据传输,基本能够串联整个应用流程。
WebSocket系列下一篇文章将会介绍在线上环境中,如何保证WebSocket的连接,以及线上可能遇到的问题。通过应对WebSocket可能出现的问题,我们能够让整个长连接更加健壮。

查看原文

hjava 发布了文章 · 2019-03-13

如何实现一个虚拟 DOM——virtual-dom 源码分析

概述

本文通过对virtual-dom的源码进行阅读和分析,针对Virtual DOM的结构和相关的Diff算法进行讲解,让读者能够对整个数据结构以及相关的Diff算法有一定的了解。

Virtual DOM中Diff算法得到的结果如何映射到真实DOM中,我们将在下一篇博客揭晓。

本文的主要内容为:

  • Virtual DOM的结构
  • Virtual DOM的Diff算法

注:这个Virtual DOM的实现并不是React Virtual DOM的源码,而是基于virtual-dom)这个库。两者在原理上类似,并且这个库更加简单容易理解。相较于这个库,React对Virtual DOM做了进一步的优化和调整,我会在后续的博客中进行分析。

Virtual DOM的结构

VirtualNode

作为Virtual DOM的元数据结构,VirtualNode位于vnode/vnode.js文件中。我们截取一部分声明代码来看下内部结构:

function VirtualNode(tagName, properties, children, key, namespace) {
    this.tagName = tagName
    this.properties = properties || noProperties //props对象,Object类型
    this.children = children || noChildren //子节点,Array类型
    this.key = key != null ? String(key) : undefined
    this.namespace = (typeof namespace === "string") ? namespace : null
    
    ...

    this.count = count + descendants
    this.hasWidgets = hasWidgets
    this.hasThunks = hasThunks
    this.hooks = hooks
    this.descendantHooks = descendantHooks
}

VirtualNode.prototype.version = version //VirtualNode版本号,isVnode()检测标志
VirtualNode.prototype.type = "VirtualNode" // VirtualNode类型,isVnode()检测标志

上面就是一个VirtualNode的完整结构,包含了特定的标签名、属性、子节点等。

VText

VText是一个纯文本的节点,对应的是HTML中的纯文本。因此,这个属性也只有text这一个字段。

function VirtualText(text) {
    this.text = String(text)
}

VirtualText.prototype.version = version
VirtualText.prototype.type = "VirtualText"

VPatch

VPatch是表示需要对Virtual DOM执行的操作记录的数据结构。它位于vnode/vpatch.js文件中。我们来看下里面的具体代码:

// 定义了操作的常量,如Props变化,增加节点等
VirtualPatch.NONE = 0
VirtualPatch.VTEXT = 1
VirtualPatch.VNODE = 2
VirtualPatch.WIDGET = 3
VirtualPatch.PROPS = 4
VirtualPatch.ORDER = 5
VirtualPatch.INSERT = 6
VirtualPatch.REMOVE = 7
VirtualPatch.THUNK = 8

module.exports = VirtualPatch

function VirtualPatch(type, vNode, patch) {
    this.type = Number(type) //操作类型
    this.vNode = vNode //需要操作的节点
    this.patch = patch //需要操作的内容
}

VirtualPatch.prototype.version = version
VirtualPatch.prototype.type = "VirtualPatch"

其中常量定义了对VNode节点的操作。例如:VTEXT就是增加一个VText节点,PROPS就是当前节点有Props属性改变。

Virtual DOM的Diff算法

了解了虚拟DOM中的三个结构,那我们下面来看下Virtual DOM的Diff算法。

这个Diff算法是Virtual DOM中最核心的一个算法。通过输入初始状态A(VNode)和最终状态B(VNode),这个算法可以得到从A到B的变化步骤(VPatch),根据得到的这一连串步骤,我们就可以知道哪些节点需要新增,哪些节点需要删除,哪些节点的属性有了变化。在这个Diff算法中,又分成了三部分:

  • VNode的Diff算法
  • Props的Diff算法
  • Vnode children的Diff算法

下面,我们就来一个一个介绍这些Diff算法。

VNode的Diff算法

该算法是针对于单个VNode的比较算法。它是用于两个树中单个节点比较的场景。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:

function walk(a, b, patch, index) {
    if (a === b) {
        return
    }

    var apply = patch[index]
    var applyClear = false

    if (isThunk(a) || isThunk(b)) {
        thunks(a, b, patch, index)
    } else if (b == null) {

        // If a is a widget we will add a remove patch for it
        // Otherwise any child widgets/hooks must be destroyed.
        // This prevents adding two remove patches for a widget.
        if (!isWidget(a)) {
            clearState(a, patch, index)
            apply = patch[index]
        }

        apply = appendPatch(apply, new VPatch(VPatch.REMOVE, a, b))
    } else if (isVNode(b)) {
        if (isVNode(a)) {
            if (a.tagName === b.tagName &&
                a.namespace === b.namespace &&
                a.key === b.key) {
                var propsPatch = diffProps(a.properties, b.properties)
                if (propsPatch) {
                    apply = appendPatch(apply,
                        new VPatch(VPatch.PROPS, a, propsPatch))
                }
                apply = diffChildren(a, b, patch, apply, index)
            } else {
                apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
                applyClear = true
            }
        } else {
            apply = appendPatch(apply, new VPatch(VPatch.VNODE, a, b))
            applyClear = true
        }
    } else if (isVText(b)) {
        if (!isVText(a)) {
            apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
            applyClear = true
        } else if (a.text !== b.text) {
            apply = appendPatch(apply, new VPatch(VPatch.VTEXT, a, b))
        }
    } else if (isWidget(b)) {
        if (!isWidget(a)) {
            applyClear = true
        }

        apply = appendPatch(apply, new VPatch(VPatch.WIDGET, a, b))
    }

    if (apply) {
        patch[index] = apply
    }

    if (applyClear) {
        clearState(a, patch, index)
    }
}

代码具体逻辑如下:

  1. 如果ab这两个VNode全等,则认为没有修改,直接返回。
  2. 如果其中有一个是thunk,则使用thunk的比较方法thunks
  3. 如果a是widget且b为空,那么通过递归将a和它的子节点的remove操作添加到patch中。
  4. 如果b是VNode的话,

    1. 如果a也是VNode,那么比较tagNamenamespacekey,如果相同则比较两个VNode的Props(用下面提到的diffProps算法),同时比较两个VNode的children(用下面提到的diffChildren算法);如果不同则直接将b节点的insert操作添加到patch中,同时将标记位置为true。
    2. 如果a不是VNode,那么直接将b节点的insert操作添加到patch中,同时将标记位置为true。
  5. 如果b是VText的话,看a的类型是否为VText,如果不是,则将VText操作添加到patch中,并且将标志位设置为true;如果是且文本内容不同,则将VText操作添加到patch中。
  6. 如果b是Widget的话,看a的类型是否为widget,如果是,将标志位设置为true。不论a类型为什么,都将Widget操作添加到patch中。
  7. 检查标志位,如果标识为为true,那么通过递归将a和它的子节点的remove操作添加到patch中。

这就是单个VNode节点的diff算法全过程。这个算法是整个diff算法的入口,两棵树的比较就是从这个算法开始的。

Prpps的Diff算法

看完了单个VNode节点的diff算法,我们来看下上面提到的diffProps算法。

该算法是针对于两个比较的VNode节点的Props比较算法。它是用于两个场景中key值和标签名都相同的情况。具体算法如下,如果不想直接阅读源码的同学也可以翻到下面,会有相关代码流程说明供大家参考:

function diffProps(a, b) {
    var diff

    for (var aKey in a) {
        if (!(aKey in b)) {
            diff = diff || {}
            diff[aKey] = undefined
        }

        var aValue = a[aKey]
        var bValue = b[aKey]

        if (aValue === bValue) {
            continue
        } else if (isObject(aValue) && isObject(bValue)) {
            if (getPrototype(bValue) !== getPrototype(aValue)) {
                diff = diff || {}
                diff[aKey] = bValue
            } else if (isHook(bValue)) {
                 diff = diff || {}
                 diff[aKey] = bValue
            } else {
                var objectDiff = diffProps(aValue, bValue)
                if (objectDiff) {
                    diff = diff || {}
                    diff[aKey] = objectDiff
                }
            }
        } else {
            diff = diff || {}
            diff[aKey] = bValue
        }
    }

    for (var bKey in b) {
        if (!(bKey in a)) {
            diff = diff || {}
            diff[bKey] = b[bKey]
        }
    }

    return diff
}

代码具体逻辑如下:

  1. 遍历a对象。

    1. 当key值不存在于b,则将此值存储下来,value赋值为undefined
    2. 当此key对应的两个属性都相同时,继续终止此次循环,进行下次循环。
    3. 当key值对应的value不同且key值对应的两个value都是对象时,判断Prototype值,如果不同则记录key对应的b对象的值;如果b对应的value是hook的话,记录b的值。
    4. 上面条件判断都不同且都是对象时,则继续比较key值对应的两个对象(递归)。
    5. 当有一个不是对象时,直接将b对应的value进行记录。
  2. 遍历b对象,将所有a对象中不存在的key值对应的对象都记录下来。

整个算法的大致流程如下,因为比较简单,就不画相关流程图了。如果逻辑有些绕的话,可以配合代码食用,效果更佳。

Vnode children的Diff算法

下面让我们来看下最后一个算法,就是关于两个VNode节点的children属性的diffChildren算法。这个个diff算法分为两个部分,第一部分是将变化后的结果b的children进行顺序调整的算法,保证能够快速的和a的children进行比较;第二部分就是将a的children与重新排序调整后的b的children进行比较,得到相关的patch。下面,让我们一个一个算法来看。

reorder算法

该算法的作用是将b节点的children数组进行调整重新排序,让ab两个children之间的diff算法更加节约时间。具体代码如下:

function reorder(aChildren, bChildren) {
    // O(M) time, O(M) memory
    var bChildIndex = keyIndex(bChildren)
    var bKeys = bChildIndex.keys  // have "key" prop,object
    var bFree = bChildIndex.free  //don't have "key" prop,array

    // all children of b don't have "key"
    if (bFree.length === bChildren.length) {
        return {
            children: bChildren,
            moves: null
        }
    }

    // O(N) time, O(N) memory
    var aChildIndex = keyIndex(aChildren)
    var aKeys = aChildIndex.keys
    var aFree = aChildIndex.free

    // all children of a don't have "key"
    if (aFree.length === aChildren.length) {
        return {
            children: bChildren,
            moves: null
        }
    }

    // O(MAX(N, M)) memory
    var newChildren = []

    var freeIndex = 0
    var freeCount = bFree.length
    var deletedItems = 0

    // Iterate through a and match a node in b
    // O(N) time,
    for (var i = 0 ; i < aChildren.length; i++) {
        var aItem = aChildren[i]
        var itemIndex

        if (aItem.key) {
            if (bKeys.hasOwnProperty(aItem.key)) {
                // Match up the old keys
                itemIndex = bKeys[aItem.key]
                newChildren.push(bChildren[itemIndex])

            } else {
                // Remove old keyed items
                itemIndex = i - deletedItems++
                newChildren.push(null)
            }
        } else {
            // Match the item in a with the next free item in b
            if (freeIndex < freeCount) {
                itemIndex = bFree[freeIndex++]
                newChildren.push(bChildren[itemIndex])
            } else {
                // There are no free items in b to match with
                // the free items in a, so the extra free nodes
                // are deleted.
                itemIndex = i - deletedItems++
                newChildren.push(null)
            }
        }
    }

    var lastFreeIndex = freeIndex >= bFree.length ?
        bChildren.length :
        bFree[freeIndex]

    // Iterate through b and append any new keys
    // O(M) time
    for (var j = 0; j < bChildren.length; j++) {
        var newItem = bChildren[j]

        if (newItem.key) {
            if (!aKeys.hasOwnProperty(newItem.key)) {
                // Add any new keyed items
                // We are adding new items to the end and then sorting them
                // in place. In future we should insert new items in place.
                newChildren.push(newItem)
            }
        } else if (j >= lastFreeIndex) {
            // Add any leftover non-keyed items
            newChildren.push(newItem)
        }
    }

    var simulate = newChildren.slice()
    var simulateIndex = 0
    var removes = []
    var inserts = []
    var simulateItem

    for (var k = 0; k < bChildren.length;) {
        var wantedItem = bChildren[k]
        simulateItem = simulate[simulateIndex]

        // remove items
        while (simulateItem === null && simulate.length) {
            removes.push(remove(simulate, simulateIndex, null))
            simulateItem = simulate[simulateIndex]
        }

        if (!simulateItem || simulateItem.key !== wantedItem.key) {
            // if we need a key in this position...
            if (wantedItem.key) {
                if (simulateItem && simulateItem.key) {
                    // if an insert doesn't put this key in place, it needs to move
                    if (bKeys[simulateItem.key] !== k + 1) {
                        removes.push(remove(simulate, simulateIndex, simulateItem.key))
                        simulateItem = simulate[simulateIndex]
                        // if the remove didn't put the wanted item in place, we need to insert it
                        if (!simulateItem || simulateItem.key !== wantedItem.key) {
                            inserts.push({key: wantedItem.key, to: k})
                        }
                        // items are matching, so skip ahead
                        else {
                            simulateIndex++
                        }
                    }
                    else {
                        inserts.push({key: wantedItem.key, to: k})
                    }
                }
                else {
                    inserts.push({key: wantedItem.key, to: k})
                }
                k++
            }
            // a key in simulate has no matching wanted key, remove it
            else if (simulateItem && simulateItem.key) {
                removes.push(remove(simulate, simulateIndex, simulateItem.key))
            }
        }
        else {
            simulateIndex++
            k++
        }
    }

    // remove all the remaining nodes from simulate
    while(simulateIndex < simulate.length) {
        simulateItem = simulate[simulateIndex]
        removes.push(remove(simulate, simulateIndex, simulateItem && simulateItem.key))
    }

    // If the only moves we have are deletes then we can just
    // let the delete patch remove these items.
    if (removes.length === deletedItems && !inserts.length) {
        return {
            children: newChildren,
            moves: null
        }
    }

    return {
        children: newChildren,
        moves: {
            removes: removes,
            inserts: inserts
        }
    }
}

下面,我们来简单介绍下这个排序算法:

  1. 检查ab中的children是否拥有key字段,如果没有,直接返回b的children数组。
  2. 如果存在,初始化一个数组newChildren,遍历a的children元素。

    1. 如果aChildren存在key值,则去bChildren中找对应key值,如果bChildren存在则放入新数组中,不存在则放入一个null值。
    2. 如果aChildren不存在key值,则从bChildren中不存在key值的第一个元素开始取,放入新数组中。
  3. 遍历bChildren,将所有achildren中没有的key值对应的value或者没有key,并且没有放入新数组的子节点放入新数组中。
  4. 将bChildren和新数组逐个比较,得到从新数组转换到bChildren数组的move操作patch(即remove+insert)。
  5. 返回新数组和move操作列表。

通过上面这个排序算法,我们可以得到一个新的b的children数组。在使用这个数组来进行比较厚,我们可以将两个children数组之间比较的时间复杂度从o(n^2)转换成o(n)。具体的方法和效果我们可以看下面的DiffChildren算法。

DiffChildren算法

function diffChildren(a, b, patch, apply, index) {
    var aChildren = a.children
    var orderedSet = reorder(aChildren, b.children)
    var bChildren = orderedSet.children

    var aLen = aChildren.length
    var bLen = bChildren.length
    var len = aLen > bLen ? aLen : bLen

    for (var i = 0; i < len; i++) {
        var leftNode = aChildren[i]
        var rightNode = bChildren[i]
        index += 1

        if (!leftNode) {
            if (rightNode) {
                // Excess nodes in b need to be added
                apply = appendPatch(apply,
                    new VPatch(VPatch.INSERT, null, rightNode))
            }
        } else {
            walk(leftNode, rightNode, patch, index)
        }

        if (isVNode(leftNode) && leftNode.count) {
            index += leftNode.count
        }
    }

    if (orderedSet.moves) {
        // Reorder nodes last
        apply = appendPatch(apply, new VPatch(
            VPatch.ORDER,
            a,
            orderedSet.moves
        ))
    }

    return apply
}

通过上面的重新排序算法整理了以后,两个children比较就只需在相同下标的情况下比较了,即aChildren的第N个元素和bChildren的第N个元素进行比较。然后较长的那个元素做insert操作(bChildren)或者remove操作(aChildren)即可。最后,我们将move操作再增加到patch中,就能够抵消我们在reorder时对整个数组的操作。这样只需要一次便利就得到了最终的patch值。

总结

整个Virtual DOM的diff算法设计的非常精巧,通过三个不同的分部算法来实现了VNode、Props和Children的diff算法,将整个Virtual DOM的的diff操作分成了三类。同时三个算法又互相递归调用,对两个Virtual DOM数做了一次(伪)深度优先的递归比较。

下面一片博客,我会介绍如何将得到的VPatch操作应用到真实的DOM中,从而导致HTML树的变化。

查看原文

赞 2 收藏 1 评论 0

hjava 发布了文章 · 2019-02-20

WebSocket 协议 RFC 文档(全中文翻译)

概述

经过半年的捣鼓,终于将 WebSocket 协议(RFC6455)全篇翻译完成。现在将所有章节全部整理到一篇文章中,方便大家阅读。如果大家想看具体的翻译文档,可以去我的GitHub中查看。

具体章节如下:

总结

通过翻译一篇文档,能够从头到尾精细的读完一篇文章,比较适合需要精读的文章和内容。大家有相关类型的需要,建议大家可以尝试下。

查看原文

赞 17 收藏 13 评论 0

hjava 发布了文章 · 2019-02-20

【译】 WebSocket 协议第六章——发送与接收消息(Sending and Receiving Data)

概述

本文为 WebSocket 协议的第六章,本文翻译的主要内容为 WebSocket 消息发送与接收相关内容。

发送与接收消息(协议正文)

6.1 发送数据

为了通过 WebSocket 连接发送一条 WebSocket 消息,终端必须遵循以下几个步骤:

  1. 终端必须保证 WebSocket 连接处于 OPEN 状态(见第 4.1 节和第 4.2.2 节)。如果 WebSocket 连接的任意一端的状态发生了改变,终端必须中止以下步骤。
  2. 终端必须将数据按照第 5.2 节定义的 WebSocket 帧进行封装。如果需要发送的数据过大或者在终端希望开始发消息时,如果数据在整体性这一点上不可用,那么终端可能会选择通过在第 5.4 节中定义的一系列帧来进行封装。
  3. 包含数据的第一帧操作码(帧操作码)必须根据第 5.2 节中的内容设置的合适的值,以便接收者将数据解析为文本或者二进制数据。
  4. 最后一个包含数据的帧的 FIN ( FIN 帧)字段必须和第 5.2 节中定义的一样设置为 1 。
  5. 如果数据被发送到了客户端,数据帧必须和第 5.3 节中定义的一样添加掩码。
  6. 如果在 WebsSocket 连接中有协商扩展(第 9 章),在这些扩展中的定义和注意事项也许要额外考虑。
  7. 被格式化的帧必须通过底层的网络连接进行传输。

6.2 接收数据

为了接收 WebSocket 数据,终端需要监听底层网络连接。输入的数据必须通过第 5.2 节定义的 WebSocket 帧进行解析。如果收到了一个控制帧(第 5.5 节),那么这个帧必须如 5.5 节中定义的方式进行处理。如果收到的是一个数据帧,那么终端必须注意 5.2 节中的定义在操作码(帧操作码)中的数据类型。在这一帧中的“应用数据”被定义为消息的数据。如果帧中包含未分片的数据(第 5.4 节),那么就认为:一条 WebSocket 消息的数据和类型被收到了。如果帧是分片数据的一部分,那么随后的帧包含的“应用数据”连起来就是数据的格式。当通过 FIN 字段(FIN帧)表示的最后一个片段被收到时,我们可以说:一条 WebSocket 消息的数据(由片段组装起来的“应用数据”数据组成)和类型(注意分片消息的第一帧)已经被收到了。接下来的数据帧必须是属于一条新的 WebSocket 消息。

扩展(第 9 章)可能改变数据如何理解的方式,具体包括消息的内容边界。扩展,除了在“应用数据”之前添加“扩展数据”之外,也可以修改“应用数据”(例如压缩它)。

像第 5.3 节中说的那样,服务端在收到客户端的数据帧时必须去除掩码。

查看原文

赞 2 收藏 1 评论 0

认证与成就

  • 获得 571 次点赞
  • 获得 6 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 6 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2015-11-02
个人主页被 3.6k 人浏览