划水咸鱼

划水咸鱼 查看完整档案

杭州编辑  |  填写毕业院校紫光云数  |  前端开发 编辑填写个人主网站
编辑

。。。

个人动态

划水咸鱼 收藏了文章 · 2019-10-28

前端与编译原理——用JS写一个JS解释器

图片描述

说起编译原理,印象往往只停留在本科时那些枯燥的课程和晦涩的概念。作为前端开发者,编译原理似乎离我们很远,对它的理解很可能仅仅局限于“抽象语法树(AST)”。但这仅仅是个开头而已。编译原理的使用,甚至能让我们利用JS直接写一个能运行JS代码的解释器。

项目地址:https://github.com/jrainlau/c...

在线体验:https://codepen.io/jrainlau/p...

一、为什么要用JS写JS的解释器

接触过小程序开发的同学应该知道,小程序运行的环境禁止new Functioneval等方法的使用,导致我们无法直接执行字符串形式的动态代码。此外,许多平台也对这些JS自带的可执行动态代码的方法进行了限制,那么我们是没有任何办法了吗?既然如此,我们便可以用JS写一个解析器,让JS自己去运行自己。

在开始之前,我们先简单回顾一下编译原理的一些概念。

二、什么是编译器

说到编译原理,肯定离不开编译器。简单来说,当一段代码经过编译器的词法分析、语法分析等阶段之后,会生成一个树状结构的“抽象语法树(AST)”,该语法树的每一个节点都对应着代码当中不同含义的片段。

比如有这么一段代码:

const a = 1
console.log(a)

经过编译器处理后,它的AST长这样:

{
  "type": "Program",
  "start": 0,
  "end": 26,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 11,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 6,
          "end": 11,
          "id": {
            "type": "Identifier",
            "start": 6,
            "end": 7,
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "start": 10,
            "end": 11,
            "value": 1,
            "raw": "1"
          }
        }
      ],
      "kind": "const"
    },
    {
      "type": "ExpressionStatement",
      "start": 12,
      "end": 26,
      "expression": {
        "type": "CallExpression",
        "start": 12,
        "end": 26,
        "callee": {
          "type": "MemberExpression",
          "start": 12,
          "end": 23,
          "object": {
            "type": "Identifier",
            "start": 12,
            "end": 19,
            "name": "console"
          },
          "property": {
            "type": "Identifier",
            "start": 20,
            "end": 23,
            "name": "log"
          },
          "computed": false
        },
        "arguments": [
          {
            "type": "Identifier",
            "start": 24,
            "end": 25,
            "name": "a"
          }
        ]
      }
    }
  ],
  "sourceType": "module"
}
常见的JS编译器有babylonacorn等等,感兴趣的同学可以在AST explorer这个网站自行体验。

可以看到,编译出来的AST详细记录了代码中所有语义代码的类型、起始位置等信息。这段代码除了根节点Program外,主体包含了两个节点VariableDeclarationExpressionStatement,而这些节点里面又包含了不同的子节点。

正是由于AST详细记录了代码的语义化信息,所以Babel,Webpack,Sass,Less等工具可以针对代码进行非常智能的处理。

三、什么是解释器

如同翻译人员不仅能看懂一门外语,也能对其艺术加工后把它翻译成母语一样,人们把能够将代码转化成AST的工具叫做“编译器”,而把能够将AST翻译成目标语言并运行的工具叫做“解释器”。

在编译原理的课程中,我们思考过这么一个问题:如何让计算机运行算数表达式1+2+3:

1 + 2 + 3

当机器执行的时候,它可能会是这样的机器码:

1 PUSH 1
2 PUSH 2
3 ADD
4 PUSH 3
5 ADD

而运行这段机器码的程序,就是解释器。

在这篇文章中,我们不会搞出机器码这样复杂的东西,仅仅是使用JS在其runtime环境下去解释JS代码的AST。由于解释器使用JS编写,所以我们可以大胆使用JS自身的语言特性,比如this绑定、new关键字等等,完全不需要对它们进行额外处理,也因此让JS解释器的实现变得非常简单。

在回顾了编译原理的基本概念之后,我们就可以着手进行开发了。

四、节点遍历器

通过分析上文的AST,可以看到每一个节点都会有一个类型属性type,不同类型的节点需要不同的处理方式,处理这些节点的程序,就是“节点处理器(nodeHandler)”

定义一个节点处理器:

const nodeHandler = {
  Program () {},
  VariableDeclaration () {},
  ExpressionStatement () {},
  MemberExpression () {},
  CallExpression () {},
  Identifier () {}
}

关于节点处理器的具体实现,会在后文进行详细探讨,这里暂时不作展开。

有了节点处理器,我们便需要去遍历AST当中的每一个节点,递归地调用节点处理器,直到完成对整棵语法书的处理。

定义一个节点遍历器(NodeIterator):

class NodeIterator {
  constructor (node) {
    this.node = node
    this.nodeHandler = nodeHandler
  }

  traverse (node) {
    // 根据节点类型找到节点处理器当中对应的函数
    const _eval = this.nodeHandler[node.type]
    // 若找不到则报错
    if (!_eval) {
      throw new Error(`canjs: Unknown node type "${node.type}".`)
    }
    // 运行处理函数
    return _eval(node)
  }

}

理论上,节点遍历器这样设计就可以了,但仔细推敲,发现漏了一个很重要的东西——作用域处理。

回到节点处理器的VariableDeclaration()方法,它用来处理诸如const a = 1这样的变量声明节点。假设它的代码如下:

  VariableDeclaration (node) {
    for (const declaration of node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? traverse(declaration.init) : undefined
      // 问题来了,拿到了变量的名称和值,然后把它保存到哪里去呢?
      // ...
    }
  },

问题在于,处理完变量声明节点以后,理应把这个变量保存起来。按照JS语言特性,这个变量应该存放在一个作用域当中。在JS解析器的实现过程中,这个作用域可以被定义为一个scope对象。

改写节点遍历器,为其新增一个scope对象

class NodeIterator {
  constructor (node, scope = {}) {
    this.node = node
    this.scope = scope
    this.nodeHandler = nodeHandler
  }

  traverse (node, options = {}) {
    const scope = options.scope || this.scope
    const nodeIterator = new NodeIterator(node, scope)
    const _eval = this.nodeHandler[node.type]
    if (!_eval) {
      throw new Error(`canjs: Unknown node type "${node.type}".`)
    }
    return _eval(nodeIterator)
  }

  createScope (blockType = 'block') {
    return new Scope(blockType, this.scope)
  }
}

然后节点处理函数VariableDeclaration()就可以通过scope保存变量了:

  VariableDeclaration (nodeIterator) {
    const kind = nodeIterator.node.kind
    for (const declaration of nodeIterator.node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined
      // 在作用域当中定义变量
      // 如果当前是块级作用域且变量用var定义,则定义到父级作用域
      if (nodeIterator.scope.type === 'block' && kind === 'var') {
        nodeIterator.scope.parentScope.declare(name, value, kind)
      } else {
        nodeIterator.scope.declare(name, value, kind)
      }
    }
  },

关于作用域的处理,可以说是整个JS解释器最难的部分。接下来我们将对作用域处理进行深入的剖析。

五、作用域处理

考虑到这样一种情况:

const a = 1
{
  const b = 2
  console.log(a)
}
console.log(b)

运行结果必然是能够打印出a的值,然后报错:Uncaught ReferenceError: b is not defined

这段代码就是涉及到了作用域的问题。块级作用域或者函数作用域可以读取其父级作用域当中的变量,反之则不行,所以对于作用域我们不能简单地定义一个空对象,而是要专门进行处理。

定义一个作用域基类Scope

class Scope {
  constructor (type, parentScope) {
    // 作用域类型,区分函数作用域function和块级作用域block
    this.type = type
    // 父级作用域
    this.parentScope = parentScope
    // 全局作用域
    this.globalDeclaration = standardMap
    // 当前作用域的变量空间
    this.declaration = Object.create(null)
  }

  /*
   * get/set方法用于获取/设置当前作用域中对应name的变量值
     符合JS语法规则,优先从当前作用域去找,若找不到则到父级作用域去找,然后到全局作用域找。
     如果都没有,就报错
   */
  get (name) {
    if (this.declaration[name]) {
      return this.declaration[name]
    } else if (this.parentScope) {
      return this.parentScope.get(name)
    } else if (this.globalDeclaration[name]) {
      return this.globalDeclaration[name]
    }
    throw new ReferenceError(`${name} is not defined`)
  }

  set (name, value) {
    if (this.declaration[name]) {
      this.declaration[name] = value
    } else if (this.parentScope[name]) {
      this.parentScope.set(name, value)
    } else {
      throw new ReferenceError(`${name} is not defined`)
    }
  }

  /**
   * 根据变量的kind调用不同的变量定义方法
   */
  declare (name, value, kind = 'var') {
    if (kind === 'var') {
      return this.varDeclare(name, value)
    } else if (kind === 'let') {
      return this.letDeclare(name, value)
    } else if (kind === 'const') {
      return this.constDeclare(name, value)
    } else {
      throw new Error(`canjs: Invalid Variable Declaration Kind of "${kind}"`)
    }
  }

  varDeclare (name, value) {
    let scope = this
    // 若当前作用域存在非函数类型的父级作用域时,就把变量定义到父级作用域
    while (scope.parentScope && scope.type !== 'function') {
      scope = scope.parentScope
    }
    this.declaration[name] = new SimpleValue(value, 'var')
    return this.declaration[name]
  }

  letDeclare (name, value) {
    // 不允许重复定义
    if (this.declaration[name]) {
      throw new SyntaxError(`Identifier ${name} has already been declared`)
    }
    this.declaration[name] = new SimpleValue(value, 'let')
    return this.declaration[name]
  }

  constDeclare (name, value) {
    // 不允许重复定义
    if (this.declaration[name]) {
      throw new SyntaxError(`Identifier ${name} has already been declared`)
    }
    this.declaration[name] = new SimpleValue(value, 'const')
    return this.declaration[name]
  }
}

这里使用了一个叫做simpleValue()的函数来定义变量值,主要用于处理常量:

class SimpleValue {
  constructor (value, kind = '') {
    this.value = value
    this.kind = kind
  }

  set (value) {
    // 禁止重新对const类型变量赋值
    if (this.kind === 'const') {
      throw new TypeError('Assignment to constant variable')
    } else {
      this.value = value
    }
  }

  get () {
    return this.value
  }
}

处理作用域问题思路,关键的地方就是在于JS语言本身寻找变量的特性——优先当前作用域,父作用域次之,全局作用域最后。反过来,在节点处理函数VariableDeclaration()里,如果遇到块级作用域且关键字为var,则需要把这个变量也定义到父级作用域当中,这也就是我们常说的“全局变量污染”。

JS标准库注入

细心的读者会发现,在定义Scope基类的时候,其全局作用域globalScope被赋值了一个standardMap对象,这个对象就是JS标准库。

简单来说,JS标准库就是JS这门语言本身所带有的一系列方法和属性,如常用的setTimeoutconsole.log等等。为了让解析器也能够执行这些方法,所以我们需要为其注入标准库:

const standardMap = {
  console: new SimpleValue(console)
}

这样就相当于往解析器的全局作用域当中注入了console这个对象,也就可以直接被使用了。

六、节点处理器

在处理完节点遍历器、作用域处理的工作之后,便可以来编写节点处理器了。顾名思义,节点处理器是专门用来处理AST节点的,上文反复提及的VariableDeclaration()方法便是其中一个。下面将对部分关键的节点处理器进行讲解。

在开发节点处理器之前,需要用到一个工具,用于判断JS语句当中的returnbreakcontinue关键字。

关键字判断工具Signal

定义一个Signal基类:

class Signal {
  constructor (type, value) {
    this.type = type
    this.value = value
  }

  static Return (value) {
    return new Signal('return', value)
  }

  static Break (label = null) {
    return new Signal('break', label)
  }

  static Continue (label) {
    return new Signal('continue', label)
  }

  static isReturn(signal) {
    return signal instanceof Signal && signal.type === 'return'
  }

  static isContinue(signal) {
    return signal instanceof Signal && signal.type === 'continue'
  }

  static isBreak(signal) {
    return signal instanceof Signal && signal.type === 'break'
  }

  static isSignal (signal) {
    return signal instanceof Signal
  }
}

有了它,就可以对语句当中的关键字进行判断处理,接下来会有大用处。

1、变量定义节点处理器——VariableDeclaration()

最常用的节点处理器之一,负责把变量注册到正确的作用域。

  VariableDeclaration (nodeIterator) {
    const kind = nodeIterator.node.kind
    for (const declaration of nodeIterator.node.declarations) {
      const { name } = declaration.id
      const value = declaration.init ? nodeIterator.traverse(declaration.init) : undefined
      // 在作用域当中定义变量
      // 若为块级作用域且关键字为var,则需要做全局污染
      if (nodeIterator.scope.type === 'block' && kind === 'var') {
        nodeIterator.scope.parentScope.declare(name, value, kind)
      } else {
        nodeIterator.scope.declare(name, value, kind)
      }
    }
  },

2、标识符节点处理器——Identifier()

专门用于从作用域中获取标识符的值。

  Identifier (nodeIterator) {
    if (nodeIterator.node.name === 'undefined') {
      return undefined
    }
    return nodeIterator.scope.get(nodeIterator.node.name).value
  },

3、字符节点处理器——Literal()

返回字符节点的值。

  Literal (nodeIterator) {
    return nodeIterator.node.value
  }

4、表达式调用节点处理器——CallExpression()

用于处理表达式调用节点的处理器,如处理func()console.log()等。

  CallExpression (nodeIterator) {
    // 遍历callee获取函数体
    const func = nodeIterator.traverse(nodeIterator.node.callee)
    // 获取参数
    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))

    let value
    if (nodeIterator.node.callee.type === 'MemberExpression') {
      value = nodeIterator.traverse(nodeIterator.node.callee.object)
    }
    // 返回函数运行结果
    return func.apply(value, args)
  },

5、表达式节点处理器——MemberExpression()

区分于上面的“表达式调用节点处理器”,表达式节点指的是person.sayconsole.log这种函数表达式。

  MemberExpression (nodeIterator) {
    // 获取对象,如console
    const obj = nodeIterator.traverse(nodeIterator.node.object)
    // 获取对象的方法,如log
    const name = nodeIterator.node.property.name
    // 返回表达式,如console.log
    return obj[name]
  }

6、块级声明节点处理器——BlockStatement()

非常常用的处理器,专门用于处理块级声明节点,如函数、循环、try...catch...当中的情景。

  BlockStatement (nodeIterator) {
    // 先定义一个块级作用域
    let scope = nodeIterator.createScope('block')

    // 处理块级节点内的每一个节点
    for (const node of nodeIterator.node.body) {
      if (node.type === 'VariableDeclaration' && node.kind === 'var') {
        for (const declaration of node.declarations) {
          scope.declare(declaration.id.name, declaration.init.value, node.kind)
        }
      } else if (node.type === 'FunctionDeclaration') {
        nodeIterator.traverse(node, { scope })
      }
    }

    // 提取关键字(return, break, continue)
    for (const node of nodeIterator.node.body) {
      if (node.type === 'FunctionDeclaration') {
        continue
      }
      const signal = nodeIterator.traverse(node, { scope })
      if (Signal.isSignal(signal)) {
        return signal
      }
    }
  }

可以看到这个处理器里面有两个for...of循环。第一个用于处理块级内语句,第二个专门用于识别关键字,如循环体内部的breakcontinue或者函数体内部的return

7、函数定义节点处理器——FunctionDeclaration()

往作用当中声明一个和函数名相同的变量,值为所定义的函数:

  FunctionDeclaration (nodeIterator) {
    const fn = NodeHandler.FunctionExpression(nodeIterator)
    nodeIterator.scope.varDeclare(nodeIterator.node.id.name, fn)
    return fn    
  }

8、函数表达式节点处理器——FunctionExpression()

用于定义一个函数:

  FunctionExpression (nodeIterator) {
    const node = nodeIterator.node
    /**
     * 1、定义函数需要先为其定义一个函数作用域,且允许继承父级作用域
     * 2、注册`this`, `arguments`和形参到作用域的变量空间
     * 3、检查return关键字
     * 4、定义函数名和长度
     */
    const fn = function () {
      const scope = nodeIterator.createScope('function')
      scope.constDeclare('this', this)
      scope.constDeclare('arguments', arguments)

      node.params.forEach((param, index) => {
        const name = param.name
        scope.varDeclare(name, arguments[index])
      })

      const signal = nodeIterator.traverse(node.body, { scope })
      if (Signal.isReturn(signal)) {
        return signal.value
      }
    }

    Object.defineProperties(fn, {
      name: { value: node.id ? node.id.name : '' },
      length: { value: node.params.length }
    })

    return fn
  }

9、this表达式处理器——ThisExpression()

该处理器直接使用JS语言自身的特性,把this关键字从作用域中取出即可。

  ThisExpression (nodeIterator) {
    const value = nodeIterator.scope.get('this')
    return value ? value.value : null
  }

10、new表达式处理器——NewExpression()

this表达式类似,也是直接沿用JS的语言特性,获取函数和参数之后,通过bind关键字生成一个构造函数,并返回。

  NewExpression (nodeIterator) {
    const func = nodeIterator.traverse(nodeIterator.node.callee)
    const args = nodeIterator.node.arguments.map(arg => nodeIterator.traverse(arg))
    return new (func.bind(null, ...args))
  }

11、For循环节点处理器——ForStatement()

For循环的三个参数对应着节点的inittestupdate属性,对着三个属性分别调用节点处理器处理,并放回JS原生的for循环当中即可。

  ForStatement (nodeIterator) {
    const node = nodeIterator.node
    let scope = nodeIterator.scope
    if (node.init && node.init.type === 'VariableDeclaration' && node.init.kind !== 'var') {
      scope = nodeIterator.createScope('block')
    }

    for (
      node.init && nodeIterator.traverse(node.init, { scope });
      node.test ? nodeIterator.traverse(node.test, { scope }) : true;
      node.update && nodeIterator.traverse(node.update, { scope })
    ) {
      const signal = nodeIterator.traverse(node.body, { scope })
      
      if (Signal.isBreak(signal)) {
        break
      } else if (Signal.isContinue(signal)) {
        continue
      } else if (Signal.isReturn(signal)) {
        return signal
      }
    }
  }

同理,for...inwhiledo...while循环也是类似的处理方式,这里不再赘述。

12、If声明节点处理器——IfStatemtnt()

处理If语句,包括ifif...elseif...elseif...else

  IfStatement (nodeIterator) {
    if (nodeIterator.traverse(nodeIterator.node.test)) {
      return nodeIterator.traverse(nodeIterator.node.consequent)
    } else if (nodeIterator.node.alternate) {
      return nodeIterator.traverse(nodeIterator.node.alternate)
    }
  }

同理,switch语句、三目表达式也是类似的处理方式。

---

上面列出了几个比较重要的节点处理器,在es5当中还有很多节点需要处理,详细内容可以访问这个地址一探究竟。

七、定义调用方式

经过了上面的所有步骤,解析器已经具备处理es5代码的能力,接下来就是对这些散装的内容进行组装,最终定义一个方便用户调用的办法。

const { Parser } = require('acorn')
const NodeIterator = require('./iterator')
const Scope = require('./scope')

class Canjs {
  constructor (code = '', extraDeclaration = {}) {
    this.code = code
    this.extraDeclaration = extraDeclaration
    this.ast = Parser.parse(code)
    this.nodeIterator = null
    this.init()
  }

  init () {
    // 定义全局作用域,该作用域类型为函数作用域
    const globalScope = new Scope('function')
    // 根据入参定义标准库之外的全局变量
    Object.keys(this.extraDeclaration).forEach((key) => {
      globalScope.addDeclaration(key, this.extraDeclaration[key])
    })
    this.nodeIterator = new NodeIterator(null, globalScope)
  }

  run () {
    return this.nodeIterator.traverse(this.ast)
  }
}

这里我们定义了一个名为Canjs的基类,接受字符串形式的JS代码,同时可定义标准库之外的变量。当运行run()方法的时候就可以得到运行结果。

八、后续

至此,整个JS解析器已经完成,可以很好地运行ES5的代码(可能还有bug没有发现)。但是在当前的实现中,所有的运行结果都是放在一个类似沙盒的地方,无法对外界产生影响。如果要把运行结果取出来,可能的办法有两种。第一种是传入一个全局的变量,把影响作用在这个全局变量当中,借助它把结果带出来;另外一种则是让解析器支持export语法,能够把export语句声明的结果返回,感兴趣的读者可以自行研究。

最后,这个JS解析器已经在我的Github上开源,欢迎前来交流~

https://github.com/jrainlau/c...

参考资料

从零开始写一个Javascript解析器

微信小程序也要强行热更代码,鹅厂不服你来肛我呀

jkeylu/evil-eval

查看原文

划水咸鱼 收藏了文章 · 2019-08-12

常见数据结构和Javascript实现总结

做前端的同学不少都是自学成才或者半路出家,计算机基础的知识比较薄弱,尤其是数据结构和算法这块,所以今天整理了一下常见的数据结构和对应的Javascript的实现,希望能帮助大家完善这方面的知识体系。

1. Stack(栈)

stack

Stack的特点是后进先出(last in first out)。生活中常见的Stack的例子比如一摞书,你最后放上去的那本你之后会最先拿走;又比如浏览器的访问历史,当点击返回按钮,最后访问的网站最先从历史记录中弹出。

Stack一般具备以下方法:

  1. push:将一个元素推入栈顶
  2. pop:移除栈顶元素,并返回被移除的元素
  3. peek:返回栈顶元素
  4. length:返回栈中元素的个数

Javascript的Array天生具备了Stack的特性,但我们也可以从头实现一个 Stack类:

function Stack() {
  this.count = 0;
  this.storage = {};

  this.push = function (value) {
    this.storage[this.count] = value;
    this.count++;
  }

  this.pop = function () {
    if (this.count === 0) {
      return undefined;
    }
    this.count--;
    var result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }

  this.peek = function () {
    return this.storage[this.count - 1];
  }

  this.size = function () {
    return this.count;
  }
}

2. Queue(队列)

queue

Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出。Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机的打印队列,排在前面的最先打印。

Queue一般具有以下常见方法:

  1. enqueue:入列,向队列尾部增加一个元素
  2. dequeue:出列,移除队列头部的一个元素并返回被移除的元素
  3. front:获取队列的第一个元素
  4. isEmpty:判断队列是否为空
  5. size:获取队列中元素的个数

Javascript中的Array已经具备了Queue的一些特性,所以我们可以借助Array实现一个Queue类型:

function Queue() {
  var collection = [];

  this.print = function () {
    console.log(collection);
  }

  this.enqueue = function (element) {
    collection.push(element);
  }

  this.dequeue = function () {
    return collection.shift();
  }

  this.front = function () {
    return collection[0];
  }

  this.isEmpty = function () {
    return collection.length === 0;
  }

  this.size = function () {
    return collection.length;
  }
}

Priority Queue(优先队列)

Queue还有个升级版本,给每个元素赋予优先级,优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现:

function PriorityQueue() {

  ...

  this.enqueue = function (element) {
    if (this.isEmpty()) {
      collection.push(element);
    } else {
      var added = false;
      for (var i = 0; i < collection.length; i++) {
        if (element[1] < collection[i][1]) {
          collection.splice(i, 0, element);
          added = true;
          break;
        }
      }
      if (!added) {
        collection.push(element);
      }
    }
  }
}

测试一下:

var pQ = new PriorityQueue();

pQ.enqueue(['gannicus', 3]);
pQ.enqueue(['spartacus', 1]);
pQ.enqueue(['crixus', 2]);
pQ.enqueue(['oenomaus', 4]);

pQ.print();

结果:

[
  [ 'spartacus', 1 ],
  [ 'crixus', 2 ],
  [ 'gannicus', 3 ],
  [ 'oenomaus', 4 ]
]

3. Linked List(链表)

Linked List

顾名思义,链表是一种链式数据结构,链上的每个节点包含两种信息:节点本身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构,存储的都是一个序列的数据,但也有很多区别,如下表:

比较维度数组链表
内存分配静态内存分配,编译时分配且连续动态内存分配,运行时分配且不连续
元素获取通过Index获取,速度较快通过遍历顺序访问,速度较慢
添加删除元素因为内存位置连续且固定,速度较慢因为内存分配灵活,只有一个开销步骤,速度更快
空间结构可以是一维或者多维数组可以是单向、双向或者循环链表

一个单向链表通常具有以下方法:

  1. size:返回链表中节点的个数
  2. head:返回链表中的头部元素
  3. add:向链表尾部增加一个节点
  4. remove:删除某个节点
  5. indexOf:返回某个节点的index
  6. elementAt:返回某个index处的节点
  7. addAt:在某个index处插入一个节点
  8. removeAt:删除某个index处的节点

单向链表的Javascript实现:

/**
 * 链表中的节点 
 */
function Node(element) {
  // 节点中的数据
  this.element = element;
  // 指向下一个节点的指针
  this.next = null;
}

function LinkedList() {
  var length = 0;
  var head = null;

  this.size = function () {
    return length;
  }

  this.head = function () {
    return head;
  }

  this.add = function (element) {
    var node = new Node(element);
    if (head == null) {
      head = node;
    } else {
      var currentNode = head;

      while (currentNode.next) {
        currentNode = currentNode.next;
      }

      currentNode.next = node;
    }
    length++;
  }

  this.remove = function (element) {
    var currentNode = head;
    var previousNode;
    if (currentNode.element === element) {
      head = currentNode.next;
    } else {
      while (currentNode.element !== element) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
  }

  this.isEmpty = function () {
    return length === 0;
  }

  this.indexOf = function (element) {
    var currentNode = head;
    var index = -1;
    while (currentNode) {
      index++;
      if (currentNode.element === element) {
        return index;
      }
      currentNode = currentNode.next;
    }

    return -1;
  }

  this.elementAt = function (index) {
    var currentNode = head;
    var count = 0;
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode.element;
  }

  this.addAt = function (index, element) {
    var node = new Node(element);
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;

    if (index > length) {
      return false;
    }

    if (index === 0) {
      node.next = currentNode;
      head = node;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      node.next = currentNode;
      previousNode.next = node;
    }
    length++;
  }

  this.removeAt = function (index) {
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if (index < 0 || index >= length) {
      return null;
    }
    if (index === 0) {
      head = currentIndex.next;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode.element;
  }
}

4. Set(集合)

set

集合是数学中的一个基本概念,表示具有某种特性的对象汇总成的集体。在ES6中也引入了集合类型Set,Set和Array有一定程度的相似,不同的是Set中不允许出现重复的元素而且是无序的。

一个典型的Set应该具有以下方法:

  1. values:返回集合中的所有元素
  2. size:返回集合中元素的个数
  3. has:判断集合中是否存在某个元素
  4. add:向集合中添加元素
  5. remove:从集合中移除某个元素
  6. union:返回两个集合的并集
  7. intersection:返回两个集合的交集
  8. difference:返回两个集合的差集
  9. subset:判断一个集合是否为另一个集合的子集

使用Javascript可以将Set进行如下实现,为了区别于ES6中的Set命名为MySet:

function MySet() {
  var collection = [];
  this.has = function (element) {
    return (collection.indexOf(element) !== -1);
  }

  this.values = function () {
    return collection;
  }

  this.size = function () {
    return collection.length;
  }

  this.add = function (element) {
    if (!this.has(element)) {
      collection.push(element);
      return true;
    }
    return false;
  }

  this.remove = function (element) {
    if (this.has(element)) {
      index = collection.indexOf(element);
      collection.splice(index, 1);
      return true;
    }
    return false;
  }

  this.union = function (otherSet) {
    var unionSet = new MySet();
    var firstSet = this.values();
    var secondSet = otherSet.values();
    firstSet.forEach(function (e) {
      unionSet.add(e);
    });
    secondSet.forEach(function (e) {
      unionSet.add(e);
    });
    return unionSet;
  }

  this.intersection = function (otherSet) {
    var intersectionSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (otherSet.has(e)) {
        intersectionSet.add(e);
      }
    });
    return intersectionSet;
  }

  this.difference = function (otherSet) {
    var differenceSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (!otherSet.has(e)) {
        differenceSet.add(e);
      }
    });
    return differenceSet;
  }

  this.subset = function (otherSet) {
    var firstSet = this.values();
    return firstSet.every(function (value) {
      return otherSet.has(value);
    });
  }
}

5. Hash Table(哈希表/散列表)

hash table

Hash Table是一种用于存储键值对(key value pair)的数据结构,因为Hash Table根据key查询value的速度很快,所以它常用于实现Map、Dictinary、Object等数据结构。如上图所示,Hash Table内部使用一个hash函数将传入的键转换成一串数字,而这串数字将作为键值对实际的key,通过这个key查询对应的value非常快,时间复杂度将达到O(1)。Hash函数要求相同输入对应的输出必须相等,而不同输入对应的输出必须不等,相当于对每对数据打上唯一的指纹。

一个Hash Table通常具有下列方法:

  1. add:增加一组键值对
  2. remove:删除一组键值对
  3. lookup:查找一个键对应的值

一个简易版本的Hash Table的Javascript实现:

function hash(string, max) {
  var hash = 0;
  for (var i = 0; i < string.length; i++) {
    hash += string.charCodeAt(i);
  }
  return hash % max;
}

function HashTable() {
  let storage = [];
  const storageLimit = 4;

  this.add = function (key, value) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      storage[index] = [
        [key, value]
      ];
    } else {
      var inserted = false;
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          storage[index][i][1] = value;
          inserted = true;
        }
      }
      if (inserted === false) {
        storage[index].push([key, value]);
      }
    }
  }

  this.remove = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index].length === 1 && storage[index][0][0] === key) {
      delete storage[index];
    } else {
      for (var i = 0; i < storage[index]; i++) {
        if (storage[index][i][0] === key) {
          delete storage[index][i];
        }
      }
    }
  }

  this.lookup = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      return undefined;
    } else {
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          return storage[index][i][1];
        }
      }
    }
  }
}

6. Tree(树)

tree

顾名思义,Tree的数据结构和自然界中的树极其相似,有根、树枝、叶子,如上图所示。Tree是一种多层数据结构,与Array、Stack、Queue相比是一种非线性的数据结构,在进行插入和搜索操作时很高效。在描述一个Tree时经常会用到下列概念:

  1. Root(根):代表树的根节点,根节点没有父节点
  2. Parent Node(父节点):一个节点的直接上级节点,只有一个
  3. Child Node(子节点):一个节点的直接下级节点,可能有多个
  4. Siblings(兄弟节点):具有相同父节点的节点
  5. Leaf(叶节点):没有子节点的节点
  6. Edge(边):两个节点之间的连接线
  7. Path(路径):从源节点到目标节点的连续边
  8. Height of Node(节点的高度):表示节点与叶节点之间的最长路径上边的个数
  9. Height of Tree(树的高度):即根节点的高度
  10. Depth of Node(节点的深度):表示从根节点到该节点的边的个数
  11. Degree of Node(节点的度):表示子节点的个数

我们以二叉查找树为例,展示树在Javascript中的实现。在二叉查找树中,即每个节点最多只有两个子节点,而左侧子节点小于当前节点,而右侧子节点大于当前节点,如图所示:

BST

一个二叉查找树应该具有以下常用方法:

  1. add:向树中插入一个节点
  2. findMin:查找树中最小的节点
  3. findMax:查找树中最大的节点
  4. find:查找树中的某个节点
  5. isPresent:判断某个节点在树中是否存在
  6. remove:移除树中的某个节点

以下是二叉查找树的Javascript实现:

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function (node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }

  findMin() {
    let current = this.root;
    while (current.left !== null) {
      current = current.left;
    }
    return current.data;
  }

  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }

  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }

  isPresent(data) {
    let current = this.root;
    while (current) {
      if (data === current.data) {
        return true;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }

  remove(data) {
    const removeNode = function (node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // node没有子节点
        if (node.left == null && node.right == null) {
          return null;
        }
        // node没有左侧子节点
        if (node.left == null) {
          return node.right;
        }
        // node没有右侧子节点
        if (node.right == null) {
          return node.left;
        }
        // node有两个子节点
        var tempNode = node.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    this.root = removeNode(this.root, data);
  }
}

测试一下:

const bst = new BST();

bst.add(4);
bst.add(2);
bst.add(6);
bst.add(1);
bst.add(3);
bst.add(5);
bst.add(7);
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));

打印结果:

1
7
6
false

7. Trie(字典树,读音同try)

trie

Trie也可以叫做Prefix Tree(前缀树),也是一种搜索树。Trie分步骤存储数据,树中的每个节点代表一个步骤,trie常用于存储单词以便快速查找,比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母,跟着树的分支可以可以拼写出一个完整的单词,每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。

Trie一般有以下方法:

  1. add:向字典树中增加一个单词
  2. isWord:判断字典树中是否包含某个单词
  3. print:返回字典树中的所有单词
/**
 * Trie的节点
 */
function Node() {
  this.keys = new Map();
  this.end = false;
  this.setEnd = function () {
    this.end = true;
  };
  this.isEnd = function () {
    return this.end;
  }
}

function Trie() {
  this.root = new Node();

  this.add = function (input, node = this.root) {
    if (input.length === 0) {
      node.setEnd();
      return;
    } else if (!node.keys.has(input[0])) {
      node.keys.set(input[0], new Node());
      return this.add(input.substr(1), node.keys.get(input[0]));
    } else {
      return this.add(input.substr(1), node.keys.get(input[0]));
    }
  }

  this.isWord = function (word) {
    let node = this.root;
    while (word.length > 1) {
      if (!node.keys.has(word[0])) {
        return false;
      } else {
        node = node.keys.get(word[0]);
        word = word.substr(1);
      }
    }
    return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
  }

  this.print = function () {
    let words = new Array();
    let search = function (node = this.root, string) {
      if (node.keys.size != 0) {
        for (let letter of node.keys.keys()) {
          search(node.keys.get(letter), string.concat(letter));
        }
        if (node.isEnd()) {
          words.push(string);
        }
      } else {
        string.length > 0 ? words.push(string) : undefined;
        return;
      }
    };
    search(this.root, new String());
    return words.length > 0 ? words : null;
  }
}

8. Graph(图)

graph

Graph是节点(或顶点)以及它们之间的连接(或边)的集合。Graph也可以称为Network(网络)。根据节点之间的连接是否有方向又可以分为Directed Graph(有向图)和Undrected Graph(无向图)。Graph在实际生活中有很多用途,比如:导航软件计算最佳路径,社交软件进行好友推荐等等。

Graph通常有两种表达方式:

Adjaceny List(邻接列表)

adj list

邻接列表可以表示为左侧是节点的列表,右侧列出它所连接的所有其他节点。

Adjacency Matrix(邻接矩阵)

adj matrix

邻接矩阵用矩阵来表示节点之间的连接关系,每行或者每列表示一个节点,行和列的交叉处的数字表示节点之间的关系:0表示没用连接,1表示有连接,大于1表示不同的权重。

访问Graph中的节点需要使用遍历算法,遍历算法又分为广度优先和深度优先,主要用于确定目标节点和根节点之间的距离,

在Javascript中,Graph可以用一个矩阵(二维数组)表示,广度优先搜索算法可以实现如下:

function bfs(graph, root) {
  var nodesLen = {};

  for (var i = 0; i < graph.length; i++) {
    nodesLen[i] = Infinity;
  }

  nodesLen[root] = 0;

  var queue = [root];
  var current;

  while (queue.length != 0) {
    current = queue.shift();

    var curConnected = graph[current];
    var neighborIdx = [];
    var idx = curConnected.indexOf(1);
    while (idx != -1) {
      neighborIdx.push(idx);
      idx = curConnected.indexOf(1, idx + 1);
    }

    for (var j = 0; j < neighborIdx.length; j++) {
      if (nodesLen[neighborIdx[j]] == Infinity) {
        nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
        queue.push(neighborIdx[j]);
      }
    }
  }

  return nodesLen;
}

测试一下:

var graph = [
  [0, 1, 1, 1, 0],
  [0, 0, 1, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0]
];

console.log(bfs(graph, 1));

打印:

{
  0: 2,
  1: 0,
  2: 1,
  3: 3,
  4: Infinity
}
最后,推荐大家使用Fundebug,一款很好用的BUG监控工具~

本文旨在向广大前端同学普及常见的数据结构,本人对这一领域也只是初窥门径,说的有差池的地方欢迎指出。也希望大家能打牢基础,在这条路上走的更高更远!

查看原文

划水咸鱼 收藏了文章 · 2019-07-31

Node.js 事件循环的完整指南

作者:Piero Borrelli

翻译:疯狂的技术宅

原文:https://blog.logrocket.com/a-...

未经允许严禁转载

每当我听到人们谈论Node.js时,就会出现很多关于究竟是什么,这项技术有什么用处,以及其未来的问题。

让我们试着解决第一部分。回答这个问题最简单的方法是列出许多 Node 技术上的定义:

  • Node.js 是一个基于 Chrome 的 V8 JavaScript 引擎构建的 Javascript 运行时环境。
  • Node.js 使用事件驱动的非阻塞 I/O 模型,使其轻量且高效。
  • Node 包生态系统(npm)是全世界最大的开源库生态系统。

但是,这些答案并不能令我满意,因为有些东西不见了。在读了上面的要点后,你可能会认为 Node.js 只是另一种 JavaScript 技术,但是如果你想要真正的理解它,最重要的是分析它是如何进行异步操作的和它的非阻塞 I/O 系统。

这是每个 Web 开发人员应该必备的知识。

准确的理解 Node 在幕后的工作原理,不仅会对这项技术了解的更多,还能够激发那些刚刚开始学习但还没深入使用的人们的兴趣。

对于已经是该领域的专业人士来说,了解它的内部和外部将使你成为一个全新、前沿的开发人员,可以根据你的需求去提高其性能。

因此,为了挖掘 Node 的世界,我们将检视其核心部分:事件循环,实际上它是负责其非阻塞 I/O 模型的部分。

A brief refresh on threads

简要刷新线程

在深入了解事件循环之前,我想先在线程上花一些时间。如果你想知道这样做的必要性,我会告诉你是为了更好地理解一个概念,我们必须先在自己的脑海中形成一个术语表,这将有助于我们识别系统的每一个部分。我们会在稍后阅读有关事件循环如何工作,以及如何将线程的概念应用于它的内容时,这最终将具有很大的优势。

每当我们运行一个程序时,就会为它创建一个实例,并且有一些内部调用线程与该实例相关。线程可以看作是我们的 CPU 必须执行的操作单元。许多不同的线程可以与程序的单个进程相关联。下面这个图可以帮你在脑海中形成这个想法:

clipboard.png

线程的简图

在讨论线程时最重要的一点是:我们的机器如何确定在什么时候处理哪个线程?

众所周知,我们机器的资源是有限的(CPU,RAM),因此正确的决定怎样分配它们是非常重要,换一种说法是,哪些操作优先于其他操作。这必须要做到,同时还要确操作不能消耗太多的时间 —— 没有人喜欢运行速度慢的电脑。

用于解决分配问题的机制称为 scheduling,它由操作系统中的调度程序管理。这背后的逻辑可能非常复杂,但总而言之,我们可以将执行此操作的两种主要方式组合在一起:

  • 多核机器:为不同的核心分配不同的线程。

clipboard.png

多核机器如何处理线程

  • 使用可减少空置时间的优化逻辑: 这是最实用的方法。如果仔细研究一下线程是如何工作的,我们将看到 OS 调度程序可以识别 CPU 什么时等待其他资源执行一个作业,由此可以分配它来同时执行其他操作。这通常发生在代价非常昂贵的 I/O 操作上,例如从硬盘读取数据。

事件循环

现在我们已经对线程如何工作有了基本的了解,接下来解决 Node.js 事件循环逻辑。通过本文,你将了解前面那些解释背后的原因,每一条都会对应到正确的位置上。

每当运行 Node 程序时,都会自动创建一个线程。这个线程是整个代码唯一执行的地方。在其中生成了一个被称为事件循环的东西。这个循环的作用是安排我们唯一的线程应该在什么时间点执行哪些操作。

详细的说明

现在让我们尝试模拟事件循环的工作原理及其工作方式。首先假设我们正在用名为 myProgram 的文件为 Node 提供信息,然后详细了解事件循环将对其进行的操作。

clipboard.png

特别是,我将首用一个简短的图来解释,说明在事件循环 tick 过程中发生的事情,然后再以更深入的方式探讨这些阶段。

clipboard.png

步骤1:performChecks

不应该单纯的认为事件循环实际上是一个循环。它有一个特定的条件,用来确定循环是否需要再次迭代。事件循环的每次迭代都被称为一个 tick

事件循环执行 tick 的条件是什么?

每当执行程序时,我们都会进行一系列需要执行的操作。这些操作主要分为三种类型:

  • 等待定时器操作(setTimeout()setInterval()setImmediate()
  • 等待处理中的操作系统任务
  • 等待需要长时间运行的操作

我稍后会详细介绍这些内容;现在让我们记住,只要其中一个操作处于挂起状态,事件循环就会执行一个新的 tick。

步骤2:执行一个 tick

对于每个循环迭代,可以分为以下阶段:

  • 阶段1: Node 查看其内部的挂起计时器集合,并检查传递给 setTimeout()setInterval() 的回调函数是否准备好在计时器过期的情况下被调用。
  • 阶段2: Node 查看其待处理 OS 任务的内部集合,并检查哪些回调函数已准备好被调用。一个例子是从机器的硬盘驱动器中完成了对文件的检索。
  • 阶段3: Node 暂停其执行,等待新事件发生。新事件包括:新的计时器完成,新的OS任务完成,新的待处理操作完成。
  • 阶段4: Node 检查是否已经准备好调用与 setImmediate() 函数相关函数。
  • 第5阶段: 管理关闭事件,用于清理程序状态。

关于事件循环的常见问题和错误观点

Node.js 是完全单线程的吗?

这是对 Node.js 的一种非常普遍的误解。 Node 运行在单个线程上,但是 Node.js 标准库中包含的一些函数并不是(例如 fs 模块函数),他们的逻辑运行在 Node.js 线程之外。这样做是为了保证程序的速度和性能。

这些其他线程运行在哪里?

Node.js 会使用名为 libuv 的特殊库模块来执行异步操作。此库还与 Node 的后台逻辑一起使用,用来管理被称为 libuv 线程池 的特殊线程池。

这个线程池由四个线程组成,用于委派对事件循环来说太重的操作。长时间运行的任务对于事件循环而言代价过于昂贵。

那么事件循环是一种类似栈的结构?

从这个意义上说,虽然在上述过程中涉及一些类似栈的结构,但更精确的答案是事件循环由一系列的阶段所组成,每个阶段都有自己的特定任务,所有阶段都以循环重复的方式去处理。如果想要知道关于事件循环确切结构的更多信息,请查看此演讲

结论

了解事件循环是使用 Node.js 的重要部分,无论你是想获得有关此技术的更多见解,了解如何提高其性能,还是找到学习新工具理由。


本文首发微信公众号:前端先锋

欢迎扫描二维码关注公众号,每天都给你推送新鲜的前端技术文章

欢迎扫描二维码关注公众号,每天都给你推送新鲜的前端技术文章

欢迎继续阅读本专栏其它高赞文章:


查看原文

划水咸鱼 收藏了文章 · 2019-07-22

Lodash 严重安全漏洞背后 你不得不知道的 JavaScript 知识

摘要: 详解原型污染。

Fundebug经授权转载,版权归原作者所有。

可能有信息敏感的同学已经了解到:Lodash 库爆出严重安全漏洞,波及 400万+ 项目。这个漏洞使得 lodash “连夜”发版以解决潜在问题,并强烈建议开发者升级版本。

我们在忙着“看热闹”或者“”升级版本”的同时,静下心来想:真的有理解这个漏洞产生的原因,明白漏洞修复背后的原理了吗?

这篇短文将从原理层面分析这一事件,相信“小白”读者会有所收获。

漏洞原因

其实漏洞很简单,举一个例子:lodash 中 defaultsDeep 方法,

_.defaultsDeep({ 'a': { 'b': 2 } }, { 'a': { 'b': 1, 'c': 3 } })

输出:

{ 'a': { 'b': 2, 'c': 3 } }

如上例,该方法:

分配来源对象(该方法的第二个参数)的可枚举属性到目标对象(该方法的第一个参数)所有解析为 undefined 的属性上

这样的操作存在的隐患:

const payload = '{"constructor": {"prototype": {"toString": true}}}'

_.defaultsDeep({}, JSON.parse(payload))

如此一来,就触发了原型污染。原型污染是指:

攻击者通过某种手段修改 JavaScript 对象的原型(prototype)

对应上例,Object.prototype.toString 就会非常不安全了。

详解原型污染

理解原型污染,需要读者理解 JavaScript 当中的原型、原型链的知识。我们先来看一个例子:

// person 是一个简单的 JavaScript 对象
let person = {name: 'lucas'}

// 输出 lucas
console.log(person.name)

// 修改 person 的原型
person.__proto__.name = 'messi'

// 由于原型链顺序查找的原因,person.name 仍然是 lucas
console.log(person.name)

// 再创建一个空的 person2 对象
let person2 = {}

// 查看 person2.name,输出 messi
console.log(person2.name)

把危害扩大化:

let person = {name: 'lucas'}

console.log(person.name)

person.__proto__.toString = () => {alert('evil')}

console.log(person.name)

let person2 = {}

console.log(person2.toString())

这段代码执行将会 alert 出 evil 文字。同时 Object.prototype.toString 这个方法会在隐式转换以及类型判断中经常被用到:

Object.prototype.toString 方法返回一个表示该对象的字符串

每个对象都有一个 toString() 方法,当该对象被表示为一个文本值时,或者一个对象以预期的字符串方式引用时自动调用。默认情况下,toString() 方法被每个 Object 对象继承。如果此方法在自定义对象中未被覆盖,toString() 返回 [object type],其中 type 是对象的类型。

如果 Object 原型上的 toString 被污染,后果可想而知。以此为例,可见 lodash 这次漏洞算是比较严重了。

再谈原型污染(NodeJS 漏洞案例)

由上分析,我们知道原型污染并不是什么新鲜的漏洞,它“随时可见”,“随处可见”。在 Nullcon HackIM 比赛中就有一个类似的 hack 题目:

'use strict';
 
const express = require('express');
const bodyParser = require('body-parser')
const cookieParser = require('cookie-parser');
const path = require('path');
 
const isObject = obj => obj && obj.constructor && obj.constructor === Object;
 
function merge(a, b) {
    for (var attr in b) {
        if (isObject(a[attr]) && isObject(b[attr])) {
            merge(a[attr], b[attr]);
        } else {
            a[attr] = b[attr];
        }
    }
    return a
}
 
function clone(a) {
    return merge({}, a);
}
 
// Constants
const PORT = 8080;
const HOST = '0.0.0.0';
const admin = {};
 
// App
const app = express();
app.use(bodyParser.json())
app.use(cookieParser());
 
app.use('/', express.static(path.join(__dirname, 'views')));
app.post('/signup', (req, res) => {
    var body = JSON.parse(JSON.stringify(req.body));
    var copybody = clone(body)
    if (copybody.name) {
        res.cookie('name', copybody.name).json({
            "done": "cookie set"
        });
    } else {
        res.json({
            "error": "cookie not set"
        })
    }
});
app.get('/getFlag', (req, res) => {
    var аdmin = JSON.parse(JSON.stringify(req.cookies))
    if (admin.аdmin == 1) {
        res.send("hackim19{}");
    } else {
        res.send("You are not authorized");
    }
});
app.listen(PORT, HOST);
console.log(`Running on http://${HOST}:${PORT}`);

这段代码的漏洞就在于 merge 函数上,我们可以这样攻击:

curl -vv --header 'Content-type: application/json' -d '{"__proto__": {"admin": 1}}' 'http://0.0.0.0:4000/signup'; 

curl -vv 'http://0.0.0.0:4000/getFlag'

首先请求 /signup 接口,在 NodeJS 服务中,我们调用了有漏洞的 merge 方法,并通过 __proto__Object.prototype(因为 {}.__proto__ === Object.prototype) 添加上一个新的属性 admin,且值为 1。

再次请求 getFlag 接口,条件语句 admin.аdmin == 1true,服务被攻击。

攻击案例出自:Prototype pollution attacks in NodeJS applications

这样的漏洞在 jQuery $.extend 中也经常见到:

对于 jQuery:如果担心安全问题,建议升级至最新版本 jQuery 3.4.0,如果还在使用 jQuery 的 1.x 和 2.x 版本,那么你的应用程序和网站仍有可能遭受攻击。

防范原型污染

了解了漏洞潜在问题以及攻击手段,那么如何防范呢?

在 lodash “连夜”发版的修复中:

我们可以清晰的看到,在遍历 merge 时,当遇见 constructor 以及 __proto__ 敏感属性,则退出程序。

那么作为业务开发者,我们需要注意些什么,防止攻击出现呢?总结一下有:

  • 冻结 Object.prototype,使原型不能扩充属性

我们可以采用 Object.freeze 达到目的:

Object.freeze() 方法可以冻结一个对象。一个被冻结的对象再也不能被修改;冻结了一个对象则不能向这个对象添加新的属性,不能删除已有属性,不能修改该对象已有属性的可枚举性、可配置性、可写性,以及不能修改已有属性的值。此外,冻结一个对象后该对象的原型也不能被修改。freeze() 返回和传入的参数相同的对象。

看代码:

Object.freeze(Object.prototype);

Object.prototype.toString = 'evil'

consoel.log(Object.prototype.toString)
ƒ toString() { [native code] }

对比:

Object.prototype.toString = 'evil'

console.log(Object.prototype.toString)
"evil"
  • 建立 JSON schema
    在解析用户输入内容是,通过 JSON schema 过滤敏感键名。
  • 规避不安全的递归性合并
    这一点类似 lodash 修复手段,完善了合并操作的安全性,对敏感键名跳过处理
  • 使用无原型对象
    在创建对象时,不采用字面量方式,而是使用 Object.create(null)
Object.create()方法创建一个新对象,使用现有的对象来提供新创建的对象的__proto__

Object.create(null) 的返回值不会链接到 Object.prototype

let foo = Object.create(null)
console.log(foo.__proto__)
// undefined

这样一来,无论如何扩充对象,都不会干扰到原型了。

  • 采用新的 Map 数据类型,代替 Object 类型

Map 对象保存键/值对,是键/值对的集合。任何值(对象或者原始值)都可以作为一个键或一个值。使用 Map 数据结构,不会存在 Object 原型污染状况。

这里总结一下 Map 和 Object 不同点::

  • Object 的键只支持 String 或者 Symbols 两种类型,Map 的键可以是任意值,包括函数、对象、基本类型
  • Map 中的键值是有序的,而 Object 中的键则不是
  • 具体 API 上的差异:比如,通过 size 属性直接获取一个 Map 的键值对个数,而 Object 的键值无法获取;再比如迭代一个 Map 和 Object 差异也比较明显
  • Map 在频繁增删键值对的场景下会有些性能优势

补充:V8,chromium 的小机灵

同样存在风险的是我们常用的 JSON.parse 方法,但是如果你运行:

JSON.parse('{ "a":1, "__proto__": { "b": 2 }}')

你会发现返回的结果如图:

复写 Object.prototype 失败了,__proto__ 属性还是我们熟悉的那个有安全感的 __proto__ 。这是因为:

V8 ignores keys named proto in JSON.parse

这个相关讨论 Doug Crockford,Brendan Eich,反正 chromium 和 JS 发明人讨论过很多次。相关 issue 和 PR:

相关 ES 语言设计的讨论:ES 语言设计的讨论:proto-and-json

在上面链接中,你能发现 JavaScript 发明人等一众大佬哦~

总之你可以记住,V8 默认使用 JSON.parse 时候会忽略 __proto__,原因当然是之前分析的安全性了。

总结

通过分析 lodash 的漏洞,以及解决方案,我们了解了原型污染的方方面面。涉及到的知识点包括但不限于:

  • Object 原型
  • 原型、原型链
  • NodeJS 相关问题
  • Object.create 方法
  • Object.freeze 方法
  • Map 数据结构
  • 深拷贝
  • 以及其他问题

这么来看,全是基础知识。也正是基础,构成了前端知识体系的方方面面。

关于Fundebug

Fundebug专注于JavaScript、微信小程序、微信小游戏、支付宝小程序、React Native、Node.js和Java线上应用实时BUG监控。 自从2016年双十一正式上线,Fundebug累计处理了10亿+错误事件,付费客户有阳光保险、核桃编程、荔枝FM、掌门1对1、微脉、青团社等众多品牌企业。欢迎大家免费试用!

查看原文

划水咸鱼 收藏了文章 · 2019-07-16

前端 100 问:能搞懂80%的请把简历给我

引言

半年时间,几千人参与,精选大厂前端面试高频 100 题,这就是「壹题」。

在 2019 年 1 月 21 日这天,「壹题」项目正式开始,在这之后每个工作日都会出一道高频面试题,主要涵盖阿里、腾讯、头条、百度、网易等大公司和常见题型。得益于大家热情参与,现在每道题都有很多答案,提供的解题思路和答案也大大增长了我的见识,到现在已累积 100 道题目,『 8000+ 』Star 了,可以说你面试中遇到过的题目,在这里肯定能发现熟悉的身影。

后期计划除了持续更新「壹题」之外,还将整理非常详细的答案解析,提供完整的思考链路,帮助大家更好的理解题目,以及题目背后的知识,「我们的目标不是背题,而是通过题目查漏补缺,温故知新」。

更多更全更详细的每日一题和答案解析,戳这里查看

第 1 - 10 题

第 1 题:(滴滴、饿了么)写 React / Vue 项目时为什么要在列表组件中写 key,其作用是什么?

解析:第 1 题

<br/>

第 2 题:['1', '2', '3'].map(parseInt) what & why ?

解析:第 2 题

<br/>

第 3 题:(挖财)什么是防抖和节流?有什么区别?如何实现?

解析:第 3 题

<br/>

第 4 题:介绍下 Set、Map、WeakSet 和 WeakMap 的区别?

解析:第 4 题

<br/>

第 5 题:介绍下深度优先遍历和广度优先遍历,如何实现?

解析:第 5 题

<br/>

第 6 题:请分别用深度优先思想和广度优先思想实现一个拷贝函数?

解析:第 6 题

<br/>

第 7 题:ES5/ES6 的继承除了写法以外还有什么区别?

解析:第 7 题

<br/>

第 8 题:setTimeout、Promise、Async/Await 的区别

解析:第 8 题

<br/>

第 9 题:(头条、微医)Async/Await 如何通过同步的方式实现异步

解析:第 9 题

<br/>

第 10 题:(头条)异步笔试题

请写出下面代码的运行结果
async function async1() {
    console.log('async1 start');
    await async2();
    console.log('async1 end');
}
async function async2() {
    console.log('async2');
}
console.log('script start');
setTimeout(function() {
    console.log('setTimeout');
}, 0)
async1();
new Promise(function(resolve) {
    console.log('promise1');
    resolve();
}).then(function() {
    console.log('promise2');
});
console.log('script end');

解析:第 10 题

<br/>

第 11 - 20 题

第 11 题:(携程)算法手写题

已知如下数组:

var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];

编写一个程序将数组扁平化去并除其中重复部分数据,最终得到一个升序且不重复的数组

解析:第 11 题

<br/>

第 12 题:(滴滴、挖财、微医、海康)JS 异步解决方案的发展历程以及优缺点。

解析:第 12 题

<br/>

第 13 题:(微医)Promise 构造函数是同步执行还是异步执行,那么 then 方法呢?

解析:第 13 题

<br/>

第 14 题:(兑吧)情人节福利题,如何实现一个 new

解析:第 14 题

<br/>

第 15 题:(网易)简单讲解一下http2的多路复用

解析:第 15 题

<br/>

第 16 题:谈谈你对TCP三次握手和四次挥手的理解

解析:第 16 题

<br/>

第 17 题:A、B 机器正常连接后,B 机器突然重启,问 A 此时处于 TCP 什么状态

如果A 与 B 建立了正常连接后,从未相互发过数据,这个时候 B 突然机器重启,问 A 此时处于 TCP 什么状态?如何消除服务器程序中的这个状态?(超纲题,了解即可)

解析:第 17 题

<br/>

第 18 题:(微医)React 中 setState 什么时候是同步的,什么时候是异步的?

解析:第 18 题

<br/>

第 19 题:React setState 笔试题,下面的代码输出什么?

class Example extends React.Component {
  constructor() {
    super();
    this.state = {
      val: 0
    };
  }
  
  componentDidMount() {
    this.setState({val: this.state.val + 1});
    console.log(this.state.val);    // 第 1 次 log

    this.setState({val: this.state.val + 1});
    console.log(this.state.val);    // 第 2 次 log

    setTimeout(() => {
      this.setState({val: this.state.val + 1});
      console.log(this.state.val);  // 第 3 次 log

      this.setState({val: this.state.val + 1});
      console.log(this.state.val);  // 第 4 次 log
    }, 0);
  }

  render() {
    return null;
  }
};

解析:第 19 题

<br/>

第 20 题:介绍下 npm 模块安装机制,为什么输入 npm install 就可以自动安装对应的模块?

解析:第 20 题

<br/>

第 21 - 30 题

第 21 题:有以下 3 个判断数组的方法,请分别介绍它们之间的区别和优劣

Object.prototype.toString.call() 、 instanceof 以及 Array.isArray()

解析:第 21 题

<br/>

第 22 题:介绍下重绘和回流(Repaint & Reflow),以及如何进行优化

解析:第 22 题

<br/>

第 23 题:介绍下观察者模式和订阅-发布模式的区别,各自适用于什么场景

解析:第 23 题

<br/>

第 24 题:聊聊 Redux 和 Vuex 的设计思想

解析:第 24 题

<br/>

第 25 题:说说浏览器和 Node 事件循环的区别

解析:第 25 题

<br/>

第 26 题:介绍模块化发展历程

可从IIFE、AMD、CMD、CommonJS、UMD、webpack(require.ensure)、ES Module、<script type="module"> 这几个角度考虑。

解析:第 26 题

<br/>

第 27 题:全局作用域中,用 const 和 let 声明的变量不在 window 上,那到底在哪里?如何去获取?。

解析:第 27 题

<br/>

第 28 题:cookie 和 token 都存放在 header 中,为什么不会劫持 token?

解析:第 28 题

<br/>

第 29 题:聊聊 Vue 的双向数据绑定,Model 如何改变 View,View 又是如何改变 Model 的

解析:第 29 题

<br/>

第 31 - 40 题

第 30 题:两个数组合并成一个数组

请把两个数组 ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'] 和 ['A', 'B', 'C', 'D'],合并为 ['A1', 'A2', 'A', 'B1', 'B2', 'B', 'C1', 'C2', 'C', 'D1', 'D2', 'D']。

解析: 第 30 题

<br/>

第 31 题:改造下面的代码,使之输出0 - 9,写出你能想到的所有解法。

for (var i = 0; i< 10; i++){
    setTimeout(() => {
        console.log(i);
    }, 1000)
}

解析:第 31 题

<br/>

第 32 题:Virtual DOM 真的比操作原生 DOM 快吗?谈谈你的想法。

解析:第 32 题

<br/>

第 33 题:下面的代码打印什么内容,为什么?

var b = 10;
(function b(){
    b = 20;
    console.log(b); 
})();

解析:第 33 题

<br/>

第 34 题:简单改造下面的代码,使之分别打印 10 和 20。

var b = 10;
(function b(){
    b = 20;
    console.log(b); 
})();

解析:第 34 题

<br/>

第 35 题:浏览器缓存读取规则

可以分成 Service Worker、Memory Cache、Disk Cache 和 Push Cache,那请求的时候 from memory cache 和 from disk cache 的依据是什么,哪些数据什么时候存放在 Memory Cache 和 Disk Cache中?

解析:第 35 题

<br/>

第 36 题:使用迭代的方式实现 flatten 函数。

解析:第 36 题

<br/>

第 37 题:为什么 Vuex 的 mutation 和 Redux 的 reducer 中不能做异步操作?

解析:第 37 题

<br/>

第 38 题:(京东)下面代码中 a 在什么情况下会打印 1?

var a = ?;
if(a == 1 && a == 2 && a == 3){
     console.log(1);
}

解析:第 38 题

<br/>

第 39 题:介绍下 BFC 及其应用。

解析:第 39 题

<br/>

第 40 题:在 Vue 中,子组件为何不可以修改父组件传递的 Prop

如果修改了,Vue 是如何监控到属性的修改并给出警告的。

解析:第 40 题

<br/>

第 41 - 50 题

第 41 题:下面代码输出什么

var a = 10;
(function () {
    console.log(a)
    a = 5
    console.log(window.a)
    var a = 20;
    console.log(a)
})()

解析:第 41题

<br/>

第 42 题:实现一个 sleep 函数

比如 sleep(1000) 意味着等待1000毫秒,可从 Promise、Generator、Async/Await 等角度实现

解析:第 42 题

<br/>

第 43 题:使用 sort() 对数组 [3, 15, 8, 29, 102, 22] 进行排序,输出结果

解析:第 43 题

<br/>

第 44 题:介绍 HTTPS 握手过程

解析:第 44 题

<br/>

第 45 题:HTTPS 握手过程中,客户端如何验证证书的合法性

解析:第 45 题

<br/>

第 46 题:输出以下代码执行的结果并解释为什么

var obj = {
    '2': 3,
    '3': 4,
    'length': 2,
    'splice': Array.prototype.splice,
    'push': Array.prototype.push
}
obj.push(1)
obj.push(2)
console.log(obj)

解析:第 46 题

<br/>

第 47 题:双向绑定和 vuex 是否冲突

解析:第 47 题

<br/>

第 48 题:call 和 apply 的区别是什么,哪个性能更好一些

解析:第 48 题

<br/>

第 49 题:为什么通常在发送数据埋点请求的时候使用的是 1x1 像素的透明 gif 图片?

解析:第 49 题

<br/>

第 50 题:(百度)实现 (5).add(3).minus(2) 功能。

例: 5 + 3 - 2,结果为 6

解析:第 50 题

<br/>

第 51 - 60 题

第 51 题:Vue 的响应式原理中 Object.defineProperty 有什么缺陷?

为什么在 Vue3.0 采用了 Proxy,抛弃了 Object.defineProperty?

解析:第 51 题

<br/>

第 52 题:怎么让一个 div 水平垂直居中

解析:第 52 题

<br/>

第 53 题:输出以下代码的执行结果并解释为什么

var a = {n: 1};
var b = a;
a.x = a = {n: 2};

console.log(a.x)     
console.log(b.x)

解析:第 53 题

<br/>

第 54 题:冒泡排序如何实现,时间复杂度是多少, 还可以如何改进?

解析:第 54 题

<br/>

第 55 题:某公司 1 到 12 月份的销售额存在一个对象里面

如下:{1:222, 2:123, 5:888},请把数据处理为如下结构:[222, 123, null, null, 888, null, null, null, null, null, null, null]。

解析:第 55 题

<br/>

第 56 题:要求设计 LazyMan 类,实现以下功能。

LazyMan('Tony');
// Hi I am Tony

LazyMan('Tony').sleep(10).eat('lunch');
// Hi I am Tony
// 等待了10秒...
// I am eating lunch

LazyMan('Tony').eat('lunch').sleep(10).eat('dinner');
// Hi I am Tony
// I am eating lunch
// 等待了10秒...
// I am eating diner

LazyMan('Tony').eat('lunch').eat('dinner').sleepFirst(5).sleep(10).eat('junk food');
// Hi I am Tony
// 等待了5秒...
// I am eating lunch
// I am eating dinner
// 等待了10秒...
// I am eating junk food

解析:第 56 题

<br/>

第 57 题:分析比较 opacity: 0、visibility: hidden、display: none 优劣和适用场景。

解析:第 57 题

<br/>

第 58 题:箭头函数与普通函数(function)的区别是什么?构造函数(function)可以使用 new 生成实例,那么箭头函数可以吗?为什么?

解析:第 58 题

<br/>

第 59 题:给定两个数组,写一个方法来计算它们的交集。

例如:给定 nums1 = [1, 2, 2, 1],nums2 = [2, 2],返回 [2, 2]。

解析:第 59 题

<br/>

第 60 题:已知如下代码,如何修改才能让图片宽度为 300px ?注意下面代码不可修改。

<img data-original="1.jpg" style="width:480px!important;”>

解析:第 60 题

<br/>

第 61 - 70 题

第 61 题:介绍下如何实现 token 加密

解析:第 61 题

<br/>

第 62 题:redux 为什么要把 reducer 设计成纯函数

解析:第 62 题

<br/>

第 63 题:如何设计实现无缝轮播

解析:第 63 题

<br/>

第 64 题:模拟实现一个 Promise.finally

解析:第 64 题

<br/>

第 65 题: a.b.c.da['b']['c']['d'],哪个性能更高?

解析:第 65 题

<br/>

第 66 题:ES6 代码转成 ES5 代码的实现思路是什么

解析:第 66 题

<br/>

第 67 题:数组编程题

随机生成一个长度为 10 的整数类型的数组,例如 [2, 10, 3, 4, 5, 11, 10, 11, 20],将其排列成一个新数组,要求新数组形式如下,例如 [[2, 3, 4, 5], [10, 11], [20]]

解析:第 67 题

<br/>

第 68 题: 如何解决移动端 Retina 屏 1px 像素问题

解析:第 68 题

<br/>

第 69 题: 如何把一个字符串的大小写取反(大写变小写小写变大写),例如 ’AbC' 变成 'aBc' 。

解析:第 69 题

<br/>

第 70 题: 介绍下 webpack 热更新原理,是如何做到在不刷新浏览器的前提下更新页面的

解析:第 70 题

<br/>

第 71 - 80 题

第 71 题: 实现一个字符串匹配算法,从长度为 n 的字符串 S 中,查找是否存在字符串 T,T 的长度是 m,若存在返回所在位置。

解析:第 71 题

<br/>

第 72 题: 为什么普通 for 循环的性能远远高于 forEach 的性能,请解释其中的原因。

image-20190512225510941

解析:第 72 题

<br/>

第 73 题: 介绍下 BFC、IFC、GFC 和 FFC

解析:第 73 题

<br/>

第 74 题: 使用 JavaScript Proxy 实现简单的数据绑定

解析:第 74 题

<br/>

第 75 题:数组里面有10万个数据,取第一个元素和第10万个元素的时间相差多少

解析:第 75 题

<br/>

第 76 题:输出以下代码运行结果

// example 1
var a={}, b='123', c=123;  
a[b]='b';
a[c]='c';  
console.log(a[b]);

---------------------
// example 2
var a={}, b=Symbol('123'), c=Symbol('123');  
a[b]='b';
a[c]='c';  
console.log(a[b]);

---------------------
// example 3
var a={}, b={key:'123'}, c={key:'456'};  
a[b]='b';
a[c]='c';  
console.log(a[b]);

解析:第 76 题

<br/>

第 77 题:算法题「旋转数组」

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4]

示例 2:

输入: [-1, -100, 3, 99] 和 k = 2
输出: [3, 99, -1, -100]
解释: 
向右旋转 1 步: [99, -1, -100, 3]
向右旋转 2 步: [3, 99, -1, -100]

解析:第 77 题

<br/>

第 78 题:Vue 的父组件和子组件生命周期钩子执行顺序是什么

解析:第 78 题

<br/>

第 79 题:input 搜索如何防抖,如何处理中文输入

解析:第 79 题

<br/>

第 80 题:介绍下 Promise.all 使用、原理实现及错误处理

解析:第 80 题

<br/>

第 81 - 90 题

第 81 题:打印出 1 - 10000 之间的所有对称数

例如:121、1331 等

解析:第 81 题

<br/>

第 82 题:周一算法题之「移动零」

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。

解析:第 82 题

<br/>

第 83 题:var、let 和 const 区别的实现原理是什么

解析:第 83 题

<br/>

第 84 题:请实现一个 add 函数,满足以下功能。

add(1);             // 1
add(1)(2);      // 3
add(1)(2)(3);// 6
add(1)(2, 3); // 6
add(1, 2)(3); // 6
add(1, 2, 3); // 6

解析:第 84 题

<br/>

第 85 题:react-router 里的 <Link> 标签和 <a> 标签有什么区别

如何禁掉 <a> 标签默认事件,禁掉之后如何实现跳转。

解析:第 85 题

<br/>

第 86 题:(京东、快手)周一算法题之「两数之和」

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解析:第 86 题

<br/>

第 87 题:在输入框中如何判断输入的是一个正确的网址。

解析:第 87 题

<br/>

第 88 题:实现 convert 方法,把原始 list 转换成树形结构,要求尽可能降低时间复杂度

以下数据结构中,id 代表部门编号,name 是部门名称,parentId 是父部门编号,为 0 代表一级部门,现在要求实现一个 convert 方法,把原始 list 转换成树形结构,parentId 为多少就挂载在该 id 的属性 children 数组下,结构如下:

// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];

解析:第 88 题

<br/>

第 89 题:设计并实现 Promise.race()

解析:第 89 题

<br/>

第 90 题:实现模糊搜索结果的关键词高亮显示

<img data-original="https://ws3.sinaimg.cn/large/...; height="800"/>

解析:第 90 题

<br/>

第 91 - 100 题

第 91 题:介绍下 HTTPS 中间人攻击

解析:第 91 题

<br/>

第 92 题:已知数据格式,实现一个函数 fn 找出链条中所有的父级 id

const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1, 11, 112]

<img data-original="https://ws1.sinaimg.cn/large/...; height="800"/>

解析:第 92 题

<br/>

第 93 题:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

示例 1:

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是(2 + 3) / 2 = 2.5

解析:第 93 题

<br/>

第 94 题:vue 在 v-for 时给每项元素绑定事件需要用事件代理吗?为什么?

解析:第 94 题

<br/>

第 95 题:模拟实现一个深拷贝,并考虑对象相互引用以及 Symbol 拷贝的情况

解析:第 95 题

<br/>

第 96 题:介绍下前端加密的常见场景和方法

解析:第 96 题

<br/>

第 97 题:React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ,那么 O(n^3) 和 O(n) 是如何计算出来的?

解析:第 97 题

<br/>

第 98 题:(京东)写出如下代码的打印结果

function changeObjProperty(o) {
  o.siteUrl = "http://www.baidu.com"
  o = new Object()
  o.siteUrl = "http://www.google.com"
} 
let webSite = new Object();
changeObjProperty(webSite);
console.log(webSite.siteUrl);

解析:第 98 题

<br/>

第 99 题:(bilibili)编程算法题

用 JavaScript 写一个函数,输入 int 型,返回整数逆序后的字符串。如:输入整型 1234,返回字符串“4321”。要求必须使用递归函数调用,不能用全局变量,输入函数必须只有一个参数传入,必须返回字符串。

解析:第 99 题

<br/>

第 100 题:(京东)请写出如下代码的打印结果

function Foo() {
    Foo.a = function() {
        console.log(1)
    }
    this.a = function() {
        console.log(2)
    }
}
Foo.prototype.a = function() {
    console.log(3)
}
Foo.a = function() {
    console.log(4)
}
Foo.a();
let obj = new Foo();
obj.a();
Foo.a();

解析:第 100 题

<br/>

❤️ 看完三件事

如果你觉得这篇内容对你挺有启发,我想邀请你帮我三个小忙:

  1. 点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-
  2. 关注我的 GitHub,让我们成为长期关系
  3. 关注公众号「高级前端进阶」,每周重点攻克一个前端面试重难点,公众号后台回复「资料」 送你精选前端优质资料。

查看原文

划水咸鱼 收藏了文章 · 2019-07-01

『前端好文整理』2019你值得拥有

年初按照惯例,是应该立下flag的时候了。

把2018年积累的一些碎片化的好文都梳理了一遍,知识体系化后学习会变得更加有目的性,从而提升学习效率(github地址)。

JS篇

数据类型

this

作用域链与闭包

原型与原型链

JS执行底层

ES6/ES7..

除此之外强烈推荐冴羽老师的ES6系列文章,深入骨髓的理解ES6中的核心。

TypeScript

Node

HTML/CSS篇

HTTP

性能&优化篇

Webpack篇

React篇

面试篇

一点感悟

在大前端的时代,要学的知识越来越多,唯有不断的学习不断的积累才能走的更远!本文也会不断的更新下去,希望能帮助到更多的前端爱好者。当然如果你有好文章推荐的话,不妨留言评论,大家一起分享,一起成长。Learn and live!奉上github

查看原文

划水咸鱼 关注了用户 · 2019-07-01

YJohn @yjohn

404

关注 46

划水咸鱼 收藏了文章 · 2019-06-10

分分钟教你用node.js写个爬虫

分分钟教你用node.js写个爬虫

写在前面

十分感谢大家的点赞和关注。其实,这是我第一次在segmentfault上写文章。因为我也是前段时间偶然之间才开始了解和学习爬虫,而且学习node的时间也不是很长。虽然用node做过一些后端的项目,但其实在node和爬虫方面我还是一个新人,这篇文章主要是想和大家分享一下node和爬虫方面的基本知识,希望对大家有帮助,也想和大家一起交流,一起学习,再次谢谢大家的支持!

对了,我开通了个人的 个人主页 ,里面有自己的技术文章,还会有个人的随想、思考和日志。以后所有的文章都会第一时间更新到这里,然后同步到其他平台。有喜欢的朋友可以没事去逛逛,再次感谢大家的支持!

一、什么是爬虫

网络爬虫(又被称为网页蜘蛛,网络机器人,在FOAF社区中间,更经常的称为网页追逐者),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁、自动索引、模拟程序或者蠕虫。
WIKIPEDIA 爬虫介绍

二、爬虫的分类

  • 通用网络爬虫(全网爬虫)
爬行对象从一些 种子URL 扩充到整个 Web,主要为门户站点搜索引擎和大型 Web 服务提供商采集数据。

通用爬虫工作流程

  • 聚焦网络爬虫(主题网络爬虫)
指选择性 地爬行那些与预先定义好的主题相关页面的网络爬虫。
  • 增量式网络爬虫
指对已下载网页采取增量式更新和 只爬行新产生的或者已经发生变化网页 的爬虫,它能够在一定程度上保证所爬行的页面是尽可能新的页面。
  • Deep Web 爬虫
爬行对象是一些在用户填入关键字搜索或登录后才能访问到的深层网页信息的爬虫。

三、爬虫的爬行策略

  • 通用网络爬虫(全网爬虫)
深度优先策略、广度优先策略

页面关系模拟树状结构

  • 聚焦网络爬虫(主题网络爬虫)
基于内容评价的爬行策略(内容相关性),基于链接结构评价的爬行策略、基于增强学习的爬行策略(链接重要性),基于语境图的爬行策略(距离,图论中两节点间边的权重)
  • 增量式网络爬虫
统一更新法、个体更新法、基于分类的更新法、自适应调频更新法
  • Deep Web 爬虫
Deep Web 爬虫爬行过程中最重要部分就是表单填写,包含两种类型:基于领域知识的表单填写、基于网页结构分析的表单填写

现代的网页爬虫的行为通常是四种策略组合的结果:

选择策略:决定所要下载的页面;
重新访问策略:决定什么时候检查页面的更新变化;
平衡礼貌策略:指出怎样避免站点超载;
并行策略:指出怎么协同达到分布式抓取的效果;

现代分布式爬虫系统

四、写一个简单网页爬虫的流程

  1. 确定爬取对象(网站/页面)
  2. 分析页面内容(目标数据/DOM结构)
  3. 确定开发语言、框架、工具等
  4. 编码 测试,爬取数据
  5. 优化

一个简单的百度新闻爬虫

确定爬取对象(网站/页面)

百度新闻http://news.baidu.com/

分析页面内容(目标数据/DOM结构)

······

确定开发语言、框架、工具等

node.js (express) + SublimeText 3

编码,测试,爬取数据

coding ···

Let's start

新建项目目录

1.在合适的磁盘目录下创建项目目录baiduNews(我的项目目录是:F:\web\baiduNews

注:因为在写这篇文章的时候用的电脑真心比较渣。安装WebStorm或者VsCode跑项目有些吃力。所以后面的命令行操作我都是在Window自带的DOS命令行窗口中执行的。

初始化package.json

1.在DOS命令行中进入项目根目录 baiduNews
2.执行npm init,初始化package.json文件

安装依赖

express (使用express来搭建一个简单的Http服务器。当然,你也可以使用node中自带的http模块)
superagent (superagent是node里一个非常方便的、轻量的、渐进式的第三方客户端请求代理模块,用他来请求目标页面)
cheerio (cheerio相当于node版的jQuery,用过jQuery的同学会非常容易上手。它主要是用来获取抓取到的页面元素和其中的数据信息)
// 个人比较喜欢使用yarn来安装依赖包,当然你也可以使用 npm install 来安装依赖,看个人习惯。
yarn add express
yarn add superagent
yarn add cheerio

依赖安装完成后你可以在package.json中查看刚才安装的依赖是否成功。
安装正确后如下图:

安装依赖包

开始coding

一、使用express启动一个简单的本地Http服务器

1、在项目根目录下创建index.js文件(后面都会在这个index文件中进行coding)

2、创建好index.js后,我们首先实例化一个express对象,用它来启动一个本地监听3000端口的Http服务。

const express = require('express');
const app = express();

// ...

let server = app.listen(3000, function () {
  let host = server.address().address;
  let port = server.address().port;
  console.log('Your App is running at http://%s:%s', host, port);
});

对,就是这么简单,不到10行代码,搭建启动一个简单的本地Http服务。

3、按照国际惯例,我们希望在访问本机地址http://localhost:3000的时候,这个服务能给我们犯规一个Hello World!index.js中加入如下代码:

app.get('/', function (req, res) {
  res.send('Hello World!');
});
此时,在DOS中项目根目录baiduNews下执行node index.js,让项目跑起来。之后,打开浏览器,访问http://localhost:3000,你就会发现页面上显示'Hellow World!'字样。
这样,在后面我们获取到百度新闻首页的信息后,就可以在访问http://localhost:3000时看到这些信息。

二、抓取百度新闻首页的新闻信息

1、 首先,我们先来分析一下百度新闻首页的页面信息。
百度新闻首页
百度新闻首页

百度新闻首页大体上分为“热点新闻”、“本地新闻”、“国内新闻”、“国际新闻”......等。这次我们先来尝试抓取左侧“热点新闻”和下方的“本地新闻”两处的新闻数据。

热点新闻DOM结构

F12打开Chrome的控制台,审查页面元素,经过查看左侧“热点新闻”信息所在DOM的结构,我们发现所有的“热点新闻”信息(包括新闻标题和新闻页面链接)都在id#pane-news<div>下面<ul><li>下的<a>标签中。用jQuery的选择器表示为:#pane-news ul li a

2、为了爬取新闻数据,首先我们要用superagent请求目标页面,获取整个新闻首页信息

// 引入所需要的第三方包
const superagent= require('superagent');

let hotNews = [];                                // 热点新闻
let localNews = [];                              // 本地新闻

/**
 * index.js
 * [description] - 使用superagent.get()方法来访问百度新闻首页
 */
superagent.get('http://news.baidu.com/').end((err, res) => {
  if (err) {
    // 如果访问失败或者出错,会这行这里
    console.log(`热点新闻抓取失败 - ${err}`)
  } else {
   // 访问成功,请求http://news.baidu.com/页面所返回的数据会包含在res
   // 抓取热点新闻数据
   hotNews = getHotNews(res)
  }
});

3、获取页面信息后,我们来定义一个函数getHotNews()来抓取页面内的“热点新闻”数据。

/**
 * index.js
 * [description] - 抓取热点新闻页面
 */
// 引入所需要的第三方包
const cheerio = require('cheerio');

let getHotNews = (res) => {
  let hotNews = [];
  // 访问成功,请求http://news.baidu.com/页面所返回的数据会包含在res.text中。
  
  /* 使用cheerio模块的cherrio.load()方法,将HTMLdocument作为参数传入函数
     以后就可以使用类似jQuery的$(selectior)的方式来获取页面元素
   */
  let $ = cheerio.load(res.text);

  // 找到目标数据所在的页面元素,获取数据
  $('div#pane-news ul li a').each((idx, ele) => {
    // cherrio中$('selector').each()用来遍历所有匹配到的DOM元素
    // 参数idx是当前遍历的元素的索引,ele就是当前便利的DOM元素
    let news = {
      title: $(ele).text(),        // 获取新闻标题
      href: $(ele).attr('href')    // 获取新闻网页链接
    };
    hotNews.push(news)              // 存入最终结果数组
  });
  return hotNews
};

这里要多说几点:

  1. async/await据说是异步编程的终级解决方案,它可以让我们以同步的思维方式来进行异步编程。Promise解决了异步编程的“回调地狱”,async/await同时使异步流程控制变得友好而有清晰,有兴趣的同学可以去了解学习一下,真的很好用。
  2. superagent模块提供了很多比如getpostdelte等方法,可以很方便地进行Ajax请求操作。在请求结束后执行.end()回调函数。.end()接受一个函数作为参数,该函数又有两个参数error和res。当请求失败,error会包含返回的错误信息,请求成功,error值为null,返回的数据会包含在res参数中。
  3. cheerio模块的.load()方法,将HTML document作为参数传入函数,以后就可以使用类似jQuery的$(selectior)的方式来获取页面元素。同时可以使用类似于jQuery中的.each()来遍历元素。此外,还有很多方法,大家可以自行Google/Baidu。

4、将抓取的数据返回给前端浏览器

前面,const app = express();实例化了一个express对象app
app.get('', async() => {})接受两个参数,第一个参数接受一个String类型的路由路径,表示Ajax的请求路径。第二个参数接受一个函数Function,当请求此路径时就会执行这个函数中的代码。
/**
 * [description] - 跟路由
 */
// 当一个get请求 http://localhost:3000时,就会后面的async函数
app.get('/', async (req, res, next) => {
  res.send(hotNews);
});
在DOS中项目根目录baiduNews下执行node index.js,让项目跑起来。之后,打开浏览器,访问http://localhost:3000,你就会发现抓取到的数据返回到了前端页面。我运行代码后浏览器展示的返回信息如下:
注:因为我的Chrome安装了JSONView扩展程序,所以返回的数据在页面展示的时候会被自动格式化为结构性的JSON格式,方便查看。

热点新闻抓取结果

OK!!这样,一个简单的百度“热点新闻”的爬虫就大功告成啦!!

简单总结一下,其实步骤很简单:

  1. express启动一个简单的Http服务
  2. 分析目标页面DOM结构,找到所要抓取的信息的相关DOM元素
  3. 使用superagent请求目标页面
  4. 使用cheerio获取页面元素,获取目标数据
  5. 返回数据到前端浏览器

现在,继续我们的目标,抓取“本地新闻”数据(编码过程中,我们会遇到一些有意思的问题)
有了前面的基础,我们自然而然的会想到利用和上面相同的方法“本地新闻”数据。
1、 分析页面中“本地新闻”部分的DOM结构,如下图:

百度新闻本地新闻

F12打开控制台,审查“本地新闻”DOM元素,我们发现,“本地新闻”分为两个主要部分,“左侧新闻”和右侧的“新闻资讯”。这所有目标数据都在id#local_newsdiv中。“左侧新闻”数据又在id#localnews-focusul标签下的li标签下的a标签中,包括新闻标题和页面链接。“本地资讯”数据又在id#localnews-zixundiv下的ul标签下的li标签下的a标签中,包括新闻标题和页面链接。

2、OK!分析了DOM结构,确定了数据的位置,接下来和爬取“热点新闻”一样,按部就班,定义一个getLocalNews()函数,爬取这些数据。

/**
 * [description] - 抓取本地新闻页面
 */
let getLocalNews = (res) => {
  let localNews = [];
  let $ = cheerio.load(res);
    
  // 本地新闻
  $('ul#localnews-focus li a').each((idx, ele) => {
    let news = {
      title: $(ele).text(),
      href: $(ele).attr('href'),
    };
    localNews.push(news)
  });
    
  // 本地资讯
  $('div#localnews-zixun ul li a').each((index, item) => {
    let news = {
      title: $(item).text(),
      href: $(item).attr('href')
    };
    localNews.push(news);
  });

  return localNews
};

对应的,在superagent.get()中请求页面后,我们需要调用getLocalNews()函数,来爬去本地新闻数据。
superagent.get()函数修改为:

superagent.get('http://news.baidu.com/').end((err, res) => {
  if (err) {
    // 如果访问失败或者出错,会这行这里
    console.log(`热点新闻抓取失败 - ${err}`)
  } else {
   // 访问成功,请求http://news.baidu.com/页面所返回的数据会包含在res
   // 抓取热点新闻数据
   hotNews = getHotNews(res)
   localNews = getLocalNews(res)
  }
});

同时,我们要在app.get()路由中也要将数据返回给前端浏览器。app.get()路由代码修改为:

/**
 * [description] - 跟路由
 */
// 当一个get请求 http://localhost:3000时,就会后面的async函数
app.get('/', async (req, res, next) => {
  res.send({
    hotNews: hotNews,
    localNews: localNews
  });
});
编码完成,激动不已!!DOS中让项目跑起来,用浏览器访问http://localhost:3000

尴尬的事情发生了!!返回的数据只有热点新闻,而本地新闻返回一个空数组[ ]。检查代码,发现也没有问题,但为什么一直返回的空数组呢?
经过一番原因查找,才返现问题出在哪里!!

一个有意思的问题

为了找到原因,首先,我们看看用superagent.get('http://news.baidu.com/').end((err, res) => {})请求百度新闻首页在回调函数.end()中的第二个参数res中到底拿到了什么内容?
// 新定义一个全局变量 pageRes
let pageRes = {};        // supergaent页面返回值

// superagent.get()中将res存入pageRes
superagent.get('http://news.baidu.com/').end((err, res) => {
  if (err) {
    // 如果访问失败或者出错,会这行这里
    console.log(`热点新闻抓取失败 - ${err}`)
  } else {
   // 访问成功,请求http://news.baidu.com/页面所返回的数据会包含在res
   // 抓取热点新闻数据
   // hotNews = getHotNews(res)
   // localNews = getLocalNews(res)
   pageRes = res
  }
});

// 将pageRes返回给前端浏览器,便于查看
app.get('/', async (req, res, next) => {
  res.send({
    // {}hotNews: hotNews,
    // localNews: localNews,
    pageRes: pageRes
  });
});
访问浏览器http://localhost:3000,页面展示如下内容:

superagent.get()请求返回值

可以看到,返回值中的text字段应该就是整个页面的HTML代码的字符串格式。为了方便我们观察,可以直接把这个text字段值返回给前端浏览器,这样我们就能够清晰地看到经过浏览器渲染后的页面。

修改给前端浏览器的返回值

app.get('/', async (req, res, next) => {
  res.send(pageRes.text)
}

访问浏览器http://localhost:3000,页面展示如下内容:

本地新闻返回页面

审查元素才发现,原来我们抓取的目标数据所在的DOM元素中是空的,里面没有数据!
到这里,一切水落石出!在我们使用superagent.get()访问百度新闻首页时,res中包含的获取的页面内容中,我们想要的“本地新闻”数据还没有生成,DOM节点元素是空的,所以出现前面的情况!抓取后返回的数据一直是空数组[ ]

本地新闻请求接口

在控制台的Network中我们发现页面请求了一次这样的接口:
http://localhost:3000/widget?id=LocalNews&ajax=json&t=1526295667917,接口状态 404
这应该就是百度新闻获取“本地新闻”的接口,到这里一切都明白了!“本地新闻”是在页面加载后动态请求上面这个接口获取的,所以我们用superagent.get()请求的页面再去请求这个接口时,接口URLhostname部分变成了本地IP地址,而本机上没有这个接口,所以404,请求不到数据。

找到原因,我们来想办法解决这个问题!!

  1. 直接使用superagent访问正确合法的百度“本地新闻”的接口,获取数据后返回给前端浏览器。
  2. 使用第三方npm包,模拟浏览器访问百度新闻首页,在这个模拟浏览器中当“本地新闻”加载成功后,抓取数据,返回给前端浏览器。

以上方法均可,我们来试试比较有意思的第二种方法

使用Nightmare自动化测试工具

Electron可以让你使用纯JavaScript调用Chrome丰富的原生的接口来创造桌面应用。你可以把它看作一个专注于桌面应用的Node.js的变体,而不是Web服务器。其基于浏览器的应用方式可以极方便的做各种响应式的交互

Nightmare是一个基于Electron的框架,针对Web自动化测试和爬虫,因为其具有跟PlantomJS一样的自动化测试的功能可以在页面上模拟用户的行为触发一些异步数据加载,也可以跟Request库一样直接访问URL来抓取数据,并且可以设置页面的延迟时间,所以无论是手动触发脚本还是行为触发脚本都是轻而易举的。

安装依赖

// 安装nightmare
yarn add nightmare

为获取“本地新闻”,继续coding...

index.js中新增如下代码:

const Nightmare = require('nightmare');          // 自动化测试包,处理动态页面
const nightmare = Nightmare({ show: true });     // show:true  显示内置模拟浏览器

/**
 * [description] - 抓取本地新闻页面
 * [nremark] - 百度本地新闻在访问页面后加载js定位IP位置后获取对应新闻,
 * 所以抓取本地新闻需要使用 nightmare 一类的自动化测试工具,
 * 模拟浏览器环境访问页面,使js运行,生成动态页面再抓取
 */
// 抓取本地新闻页面
nightmare
.goto('http://news.baidu.com/')
.wait("div#local_news")
.evaluate(() => document.querySelector("div#local_news").innerHTML)
.then(htmlStr => {
  // 获取本地新闻数据
  localNews = getLocalNews(htmlStr)
})
.catch(error => {
  console.log(`本地新闻抓取失败 - ${error}`);
})

修改getLocalNews()函数为:

/**
 * [description]- 获取本地新闻数据
 */
let getLocalNews = (htmlStr) => {
  let localNews = [];
  let $ = cheerio.load(htmlStr);

  // 本地新闻
  $('ul#localnews-focus li a').each((idx, ele) => {
    let news = {
      title: $(ele).text(),
      href: $(ele).attr('href'),
    };
    localNews.push(news)
  });

  // 本地资讯
  $('div#localnews-zixun ul li a').each((index, item) => {
    let news = {
      title: $(item).text(),
      href: $(item).attr('href')
    };
    localNews.push(news);
  });

  return localNews
}

修改app.get('/')路由为:

/**
 * [description] - 跟路由
 */
// 当一个get请求 http://localhost:3000时,就会后面的async函数
app.get('/', async (req, res, next) => {
  res.send({
    hotNews: hotNews,
    localNews: localNews
  })
});
此时,DOS命令行中重新让项目跑起来,浏览器访问https://localhost:3000,看看页面展示的信息,看是否抓取到了“本地新闻”数据!

至此,一个简单而又完整的抓取百度新闻页面“热点新闻”和“本地新闻”的爬虫就大功告成啦!!

最后总结一下,整体思路如下:

  1. express启动一个简单的Http服务
  2. 分析目标页面DOM结构,找到所要抓取的信息的相关DOM元
  3. 使用superagent请求目标页面
  4. 动态页面(需要加载页面后运行JS或请求接口的页面)可以使用Nightmare模拟浏览器访问
  5. 使用cheerio获取页面元素,获取目标数据

完整代码

爬虫完整代码GitHub地址:完整代码

后面,应该还会做一些进阶,来爬取某些网站上比较好看的图片(手动滑稽),会牵扯到并发控制反-反爬虫的一些策略。再用爬虫取爬去一些需要登录和输入验证码的网站,欢迎到时大家关注和指正交流。

我想说

再次感谢大家的点赞和关注和评论,谢谢大家的支持,谢谢!我自己觉得我算是一个爱文字,爱音乐,同时也喜欢coding的半文艺程序员。之前也一直想着写一写技术性和其他偏文学性的文章。虽然自己的底子没有多么优秀,但总是觉得在写文章的过程中,不论是技术性的还是偏文学性的,这个过程中可以督促自己去思考,督促自己去学习和交流。毕竟每天忙忙碌碌之余,还是要活出自己不一样的生活。所以,以后如果有一些好的文章我会积极和大家分享!再次感谢大家的支持!
查看原文

划水咸鱼 收藏了文章 · 2019-05-21

SegmentFault 技术周刊 Vol.35 - WebGL:打开网页看大片

clipboard.png

WebGL 可以说是 HTML5 技术生态链中最为令人振奋的标准之一,它把 Web 带入了 3D 的时代。

初识 WebGL

先通过几个使用 WebGL 的网站来认识下 WebGL 的魅力吧~

温馨提示:浏览以下网页需要浏览器支持 WebGL 功能。:)

20 个让人惊艳的运用 WebGL 的例子

http://stars.chromeexperiment...

http://www.nowyouseeme.movie

http://webglsamples.org/

WebGL 入门

WebGL 技术储备指南

本文的预期读者是:不熟悉图形学,熟悉前端,希望了解或系统学习 WebGL 的同学。

本文不是 WebGL 的概述性文章,也不是完整详细的 WebGL 教程。本文只希望成为一篇供 WebGL 初学者使用的提纲。

WebGL 初探

用更专业的描述讲,WebGL (Web Graphics Library) 是一个用以渲染交互式 3D 和 2D 图形的无需插件且兼容下一代浏览器的 JavaScript API,通过 HTML5 中 <canvas> 元素实现功能。WebGL 是由 Khronos Group 集团制定,而非 W3C 组织。目前,我们可以使用的是 WebGL 第一个版本,它继承自 OpenGL ES 2.0 。而 OpenGL ES (OpenGL for Embedded Systems) 是 OpenGL 三维图形 API 的子集,针对手机、PDA 和游戏主机等嵌入式设备而设计。

WebGL 绘制三角形

本篇章将讲解如何使用 WebGL 绘制三角形,因为很多 3D 图形都是使用三角形为基础进行渲染的,所以有些对 GPU 性能指标的评价就是渲染三角形的能力。

WebGL 与 THREE 入门 Lesson1:计算图形成像原理简介

这篇文章我们将简单讲一下成像原理,以及附上的GPU绘制流水线。这个成像原理到绘制流水线的中间过渡可能有点跳跃。我当初学习的时候就在这里卡住了。因为学习过程中没有理解记录下来这个过程,所以现在没有办法还原自己的想法和大家分享,也没法给大家一些启示。所以随时随地记录下自己的想法真的很重要啊!!虽然可能不准确但是很真实啊!

webgl 开发第一道坎:矩阵与坐标变换

  • 一、齐次坐标
  • 二、矩阵迷宫
  • 三、模型矩阵与模型视图矩阵
  • 四、透视矩阵
  • 五、屏幕坐标变换

JavaScript Canvas——“WebGL”的注意要点

Threejs

Three.js中文文档

Three.js是一个在浏览器中使用WebGL创建3D变得容易的库。当你想创建一个立方体的时候,使用原生WebGL来创建,需要写数百行JavaScript代码,如果使用Three.js只需要几行代码就可以完成。

Three.js学习笔记

一个典型的Three.js程序至少要包括渲染器(Renderer)、场景(Scene)、照相机(Camera),以及你在场景中创建的物体。

我的世界:一个村落(其一)

本文是一篇three.js的入门文章,将介绍three.js的一些基本概念,并一步步搭建一个简单的场景模型:

图片描述

我的世界:一个村落(其二)

现在我们对three.js的基本元素与如何用three.js搭建场景有了一定的了解后,本篇我们开始搭建村落中山坡,房屋等对象。

threejs构建web三维视图入门教程

本文是一篇简单的webGL+threejs构建web三维视图的入门教程,你可以了解到利用threejs创建简单的三维图形,并且控制图形运动。

  • 一、创建场景
  • 二、绘制图形
  • 三、创建3d对象

    • 创建一个自己的对象
    • 外部导入.obj文件
  • 四、动画

    • 基本的动画
    • 对动画进行控制

threejs 绘制地球、飞机、轨迹

首先我们来看下要实现的效果:

clipboard.png

图片描述

Three.js 入门:如何使用并绘制基础 3D 图形

在以上内容中,只写到了 Three.js 中提供的基础功能,还有很多高级的功能需要大家去探索。希望大家看完这篇文章后能对 Three.js 有一个初步的了解,并能够使用 Three.js 绘制出基础的 3D 图形。

H5实例教学--3D全景(ThreeJs全景Demo)

在现在市面上很多全景H5的环境下,要实现全景的方式有很多,可以用css3直接构建也可以用基于threeJs的库来实现,还有很多别的制作全景的软件使用。本教学适用于未开发过3D全景的工程狮。

ThreeJS中的点击与交互——Raycaster的用法

我们的手机屏幕是二维的,但是我们展示物体的世界是三维的,当我们在构建一个物体的时候我们是以一个三维世界既是世界坐标来构建,而转化为屏幕坐标展示在我们眼前,则需要经历多道矩阵变化,中间webGL替我们操作了许多事情。

高仿腾讯QQ Xplan(X计划)的H5页面(1):threejs创建地球

这个h5的主要玩法很简单:地球自转的时候会播放背景音乐(比如海浪声),为了找到这个声音是从哪个地球上哪个地方传来的,需要长按下方的按钮,这时地球会自动转动到目标地点,然后镜头拉近,穿过云层,最后你会看到和这段声音相关的视频内容;松开手之后,上面的过程会倒退回去,地球又开始自转,播放着下段神秘的背景音乐。

Threejs 开发 3D 地图实践总结

前段时间连续上了一个月班,加班加点完成了一个3D攻坚项目。也算是由传统web转型到webgl图形学开发中,坑不少,做了一下总结分享。

  • 1、法向量问题
  • 2、光源与面块颜色
  • 3、POI标注
  • 4、点击拾取问题
  • 5、性能优化
  • 6、面点击移动到屏幕中央
  • 7、2/3D切换
  • 8、3D中地理级别
  • 9、poi碰撞

A-Frame.js 学习&文档翻译(一)实体

A-Frame是Mozilla 开源 web 虚拟现实框架,他能够非常方便的创建VR视口,载入部分格式的模型,设置照相机等,这为对计算机图形学不是很了解的同学,减轻了好多负担。我分别用了threeJS和A-Frame.js做了两个小项目,全英文文档看的好累,就顺便翻译了部分文档,之后会分享threeJS与模型导出与加载的一些坑。

简单一招搞定 three.js 屏幕适配

做过手机 H5 的同学可能会觉得屏幕适配挺麻烦。原因是设计师提供的设计稿尺寸比固定,但是前端开发者却要适配不同大小、长宽比的目标设备。适配的终极目标无非是最大程度把主体内容优雅地呈现给用户。开发和设计如果没有协调好的话可能会妥协比较丑陋的方案,例如由于设计比例问题,为了照顾主体内容不被裁剪,只好设备两边,或者上下留黑边这种。

不过在 3D 的世界里,我们不用担心会有黑边的问题,因为 3D 场景是无限延伸的,总能填满任何比例的屏幕。

应用

利用threejs实现3D全景图

基于HTML5和WebGL的3D网络拓扑结构图

利用HT For Web中的3D组件来实现了一个小例子,整体实现的效果图:

图片描述

D3 力导向图和 WebGL 的整合使用

D3 是目前最流行的数据可视化库,WebGL 是目前 Web 端最快的绘制技术。由于性能问题的局限,将两者结合的尝试越来越多(如),本文将尝试用 D3 的力导向图 和 Three.js 和 PixiJS 结合。全文阅读完大概 5 分钟,因为你重点应该看代码。

从3dMax导出供threeJS使用的带动作模型与加载

在自己做的一个小玩意中,发现要从3dMax中导出js文件供给threeJS使用,真是太多坑了!所以打算详细记录一下方法,好像开发会3dMax的比较少,但是至少可以帮助开发与美工更好的沟通与交流。在文末,我会附上一个可加载的js模型,方便学习~

Canvas + WebGL中文艺术字渲染

用canvas原生api可以很容易地绘制文字,但是原生api提供的文字效果美化功能十分有限。如果想要绘制除描边、渐变这些常用效果以外的艺术字,又不用耗时耗力专门制作字体库的话,利用WebGL进行渲染是一种不错的选择。

这篇文章主要讲述如何利用canvas原生api获取文字像素数据,并对其进行笔画分割、边缘查找、法线计算等处理,最后将这些信息传入着色器,实现基本的光照立体文字。

利用canvas原生api获取文字像素信息的好处是,可以绘制任何浏览器支持的字体,而无需制作额外的字体文件;而缺陷是对一些高级需求(如笔画分割)的数据处理,时间复杂度较高。但对于个人项目而言,这是做出自定义艺术字效果比较快捷的方法。

基于 WebSocket 实现 WebGL 3D 拓扑图实时数据通讯同步(一)

在这里我们用比较易上手的 Node.js 的 Socket.IO 做通讯框架,Socket.IO 让长连接通讯变得无比简单,服务器再也不用等待客户端的请求就可以直接给客户端发送消息,根据这样的特性就可以实现数据通讯同步的问题。

基于 WebSocket 实现 WebGL 3D 拓扑图实时数据通讯同步(二)

有了前面的知识储备,我们就可以来真正实现我们 3D 拓扑图组件上节点位置信息的实时数据同步了,毋庸置疑,节点的位置信息必须是在服务端统筹控制,才能达到实时数据同步,也就是说,我们必须在服务端创建 DataModel 来管理节点,创建 ForceLayout 弹力布局节点位置,并在节点位置改变的过程中,实时地将位置信息推送到客户端,让每个客户端都更新各自页面上面的节点位置。

HTML5,不只是看上去很美(第二弹:打造最美3D机房)

在html5里面使用3D已经不是什么高深技术,它的基础是WebGL,一个OpenGL的浏览器子集,支持大部分主要3D功能接口。目前最新的浏览器都有比较好的支持,IE需要到11(是的,你没有看错)。

clipboard.png

打造最美HTML5 3D机房(第三季新增资产管理、动环监控)

,第一期重点放在三维呈现和静态的资产管理上,第二期着重动环监控,这样基本上一个比较完整的数据中心监控系统就出来了。

clipboard.png

打造最美HTML5 3D机房(MONO哥强势归来,第四季惊艳发布)

clipboard.png

[2016年末巨献] — HTML5可交互地铁线路图(第二季:帝都进阶版)

图片描述

基于HTML5和WebGL的三维可视立体动态流程图

图片描述

WebGL实现HTML5贪吃蛇3D游戏

90来行所有JS源代码如下,各位游戏高手不要喷我,肯定很多人可以写得更精炼,但我只想通过这个玩一玩3D,HTML5和WebGL,包括给整天搞企业应用的自己换换脑子思考些新元素。

WebVR

浅谈 WebVR

WebVR 是早期和实验性的 JavaScript API,它提供了访问如 Oculus Rift 和 Google Cardboard 等 VR 设备功能的 API。
在 Web 上开发 VR 应用,有下面三种(潜在)方式:

  • JavaScript, Three.js 与 监听设备方向(Device Orientation)
  • JavaScript, Three.js 与 WebVR
  • CSS 与 WebVR(仍处于非常早期阶段)

由于 WebVR 仍处于草案阶段并可能会有所改变,所以建议你基于 webvr-boilerplate 进行 WebVR 开发。

WebVR如此近-three.js的WebVR示例解析

WebVR是一个实验性的Javascript API,允许HMD(head-mounted displays)连接到web apps,同时能够接受这些设备的位置和动作信息。这让使用Javascript开发VR应用成为可能(当然已经有很多接口API让Javascript作为开发语言了,不过这并不影响我们为WebVR感到兴奋)。而让我们能够立马进行预览与体验,移动设备上的chrome已经支持了WebVR并使手机作为一个简易的HMD。手机可以把屏幕分成左右眼视觉并应用手机中的加速度计、陀螺仪等感应器,你需要做的或许就只是买一个cardboard。

VR进化论|教你搭建通用的WebVR工程

本文旨在介绍如何搭建WebVR工程以支持多场景开发。
实现功能

  • VR多场景模块化开发
  • 支持VR场景创建、回收、切换
  • 项目自动化构建与压缩打包
  • 支持es7/6

【WebVR教程翻译】超简单!用A-frame快速打造你的VR网站

A-frame是由three.js封装而来的一组库,使用它可以方便地构建跨平台Web VR应用。如果你对它毫无概念,还没有准备好继续往下读,可以先看看A-frame官方示例,了解了解这个它是工作的,以及它能用来做什么。

在这篇文章中,我将教会你如何创建一个VR网站,你可以体验到在两个360°全景之间切换。实现这一效果,我们将会用到一些A-frame的特定代码和一点点JavaScript的代码。

VR大潮来袭 ---前端开发能做些什么

去年谷歌和火狐针对WebVR提出了WebVR API的标准,顾名思义,WebVR即web + VR的体验方式,我们可以戴着头显享受沉浸式的网页,新的API标准让我们可以使用js语言来开发。今天,约克先森将介绍如何开发一个WebVR网页,在此之前,我们有必要了解WebVR的体验方式。

WebVR开发教程——深度剖析

最近WebVR API 1.1已经发布,2.0草案也在拟定中,在我看来,WebVR走向大众浏览器是早晚的事情了,今天本人将对WebVR开发环境和开发流程进行深入介绍。

本期完
:)


欢迎关注 SegmentFault 微信公众号 :)

clipboard.png

查看原文

划水咸鱼 收藏了文章 · 2019-05-07

从灭霸的无限手套说起

本文不是技术文章,只是单纯记录下

最近妇联4在热映,先剧透两个精彩片段。
图片描述图片描述

前两天看到Google搜索有个彩蛋,搜索灭霸或者thanos,点击右边的无限手套触发彩蛋,打个响指,消灭一半的搜索结果条目,消失特效类似电影里的。
图片描述

首先分析下这个彩蛋主要包括

  1. 点击手套动画效果
  2. 消失的搜索条目的粒子效果

接下来是从以下方面着手

  1. html页面
  2. DOMcanvas
  3. 粒子效果
  4. 其他包括音效、页面平滑滚动等

html页面(扒网页)

首先排除扒Google搜索页面,因为服务器用的是国内阿里云访问不了。

然后就打算扒百度的搜索页,用的是PHP程序,我知道的能够获取页面代码的有file_get_contentcURL函数,虽然拿到了页面代码,但是只要搜索结果那些DOM的话用正则比较麻烦,搜了下找到phpQuery库,它能像jQuery操作那样拿到指定DOM,和Node.js的cheerio包类似。但是百度的这个页面样式类是动态的,还要把整个style内容也输出,而且很多图片大概是经过了什么处理,没权限显示不了,遂放弃。

接着扒斗鱼的直播列表页,返回一堆乱码,实力告退了。最后选择了相似的企鹅电竞直播列表页,页面算是搞定了。

DOM转canvas

前端有html2canvasdom-to-image两个库可以把页面指定元素转化为画布或图片,html2canvas比较有名些,早期我也是用这个库做前端截图功能(https://imusic.github.io/clip/),但是它对CSS3的处理并不好,后来我发现了dom-to-image这个库,它对CSS3的处理就比较好了,而且体积更小,所以又用这个库替换了(https://demo.vczhan.com/clip/)。
图片描述

不过因为要转化的内容里有跨域的图片,canvas对此做了限制,我们需要对图片做代理处理。dom-to-image这个库并没有提供相关的代理插件,最后还是用html2canvas这个库。页面没有复杂的元素,并且这个库近来做了更新,对CSS3支持好了些,作者还提供了两种语言的代理,分别是Python版本的和Node.js版本的,不过我选择了其他人写的PHP版本。前端只要配置相关参数就可以。服务器端则会在文件目录下新建cache目录存放图片并返回给前端渲染到画布上。(不知能否改成不存储图片文件而是改成输出base64或者blob数据)

html2canvas(node, {
  proxy: 'html2canvasproxy.php'
}).then(canvas => {
  // do stuff
})

粒子效果

粒子效果比较难的部分是怎么调整各个参数到合适的值还要保证动画不卡。其实js计算过程并不会让动画卡顿,主要瓶颈在渲染阶段。

渲染部分原来用遍历粒子直接绘制,但因为粒子较多,动画看起来有点卡。

render() {
  context.clearRect(0, 0, sw, sh)

  let particles = this.particles

  for (let i = 0, particle; particle = particles[i++];) {
    if (particle.state === 'dead') continue

    context.save()
    context.translate(particle.x, particle.y)

    context.fillStyle = particle.color
    context.globalAlpha = particle.alpha
    context.beginPath()
    context.fillRect(0, 0, 1, 1)
    context.restore()
  }
}

后来改成每次渲染时,先得到空白画布的图像数据,然后遍历粒子,给图像数据对应的位置加上rgba,最后将图像数据放回画布。

render() {
  // context.clearRect(0, 0, sw, sh)
  let particles = this.particles

  const imageData = context.createImageData(sw, sh)
  const buffer32 = new Uint32Array(imageData.data.buffer)

  for (let i = 0, particle; particle = particles[i++];) {
    if (particle.state === 'dead') continue

    const {x, y, color: {r, g, b}, alpha: a} = particle
    const pos = y * sw + x

    buffer32[pos] = r | (g << 8) | (b << 16) | (a << 24)
  }

  context.putImageData(imageData, 0, 0)
}

Google那个页面是用了多个canvas,可以参考下面的粒子
https://codepen.io/birjolaxew...

其他

其他就是些细节调整,比如点击手套的过渡动画并加上音效,过渡时间和延迟要慢慢调到合适的使动画与音效对应。当某个DOM要消失也要加上音效,并且页面平滑滚动,使其位于屏幕中心,可以直接用scrollIntoView这个方法。

node.scrollIntoView({behavior: 'smooth', block: 'center'})

素材都可以从Google彩蛋页里提取,还有其他一些细节就不逐一赘述了。

最后放上本次的demo

查看原文

认证与成就

  • 获得 2 次点赞
  • 获得 31 枚徽章 获得 1 枚金徽章, 获得 11 枚银徽章, 获得 19 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-05-03
个人主页被 585 人浏览