HTML parser和querySelector实现分析

前言

  • 最近在学习React Native的开发，把web端的网站转成app，由于部分api的缺失，需要从web的HTML里提取信息，那么就需要一个解析HTML的工具。
  • cheerio就是其中一个有名的库，但遗憾的是cheerio本身不支持在React Native环境运行。
  • 记得之前看过微信团队的一个开源项目kbone是通过在小程序中模拟浏览器环境让面向web端开发的应用也能运行在小程序中。里面就包含了HTML parser和querySelector的实现，这两个的实现主要是
    参考了HTMLParser和Jquery的sizzle。
  • 具体实现可以到上面的仓库查看相关代码，下面介绍实现的主要逻辑

分析

  1. HTML parser
    1. 建立一个栈stack
    2. 抛开正则表达式不讲，最重要的逻辑是把遇到的开始标签(opening tag)时，会做如下操作：
      1. 如果栈不为空，就把新的标签加到栈顶的children数组中
      2. 把它存到stack
    3. 当遇到结束标签(closing tag)时，把stack中相同类型的标签压出
  2. querySelector
    1. 初始的时候，遍历parser解析出的HTML tree，把node的id，class和tag分别加入到idMap, classMap，tagMap中
    2. selector的解析，一般我们读的时候是从左往右读的，但这个实现的解析的是从右往右的。
      1. 根据最右的规则，决定是从idMap, classMap还是tagMap从取出最初的候选列表
      2. 从右往左，根据一个个规则去过滤（收窄）候选列表
      • 这样做的好处，能想到的是，从右往左实际上是一种自下而上的方式，可以避免自上而下需要递归的问题。
      1. 去重和排序候选列表。去重不说，排序它使用的方法是，先找到两个node的最小的共同祖先A，设B为A下的子节点（B可能为node的祖先或者node本身），根据两个B的先后顺序，来决定node的先后顺序

感想

  1. JS现在可以做跨平台的开发，虽然有些方法在浏览器中是有的，但可能别的平台没有，这时候就需要开发者去了解DOM API的实现方式。
  2. 假如浏览器的querySelector也是类似上述的实现方式，那么对于CSS selector的优化，可以做如下三点:
    1. 优先度应该是id，class再到tag，class方面尽量使用出现频率较少的那个，尽量不要用*，因为用*相当于选择了所有的tag类型
    2. 关系选择器方面，尽量不要用跨层的空格selector，而要使用表示直接关系的
    3. selector要尽量短，因为每多一层就多一次判断

Leetcode 84 Largest Rectangle in Histogram分析

题目链接

根据题解得到的思路：

  1. 矩形大小等于区间内最低柱形高度乘以区间的大小
  2. 最大矩形等于以各柱形为最低高度时围绕它形成的最大区间的矩形大小的最大值
  3. 每个柱形形成的区间的左右边界为小于它高度且最靠近的矩形或者柱形数组的边界

为了求出这些区间，题解中使用了一个栈结构

栈具有如下性质

  1. 每个柱形的index都会压入栈中
  2. 柱形A的index入栈前先把栈中高度小于A的index出栈，保证栈中index所指向的高度保持依次增大的性质。

换句话说栈中的上一个元素其实是当前元素的左界（因为是依次增大），
当元素出栈时（大于新加入的元素），就是右界确定的时候，左右界确定后，区间矩形大小就能求出了

参考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> stack = { -1 };
        int heightsLength = heights.size();
        int maxArea = 0;
        int backIndex = -1;
        for (int i = 0;i < heightsLength;i++)
        {
          backIndex = stack.back();
          while(backIndex != -1 && heights[backIndex] > heights[i])
          {
            maxArea = max((i - stack[stack.size() - 2] - 1) * heights[backIndex], maxArea);
            stack.pop_back();
            backIndex = stack.back();
          }
          stack.push_back(i);
        }
        backIndex = stack.back();
        while(backIndex != -1)
        {
          maxArea = max(maxArea, (heightsLength - stack[stack.size() - 2] - 1) * heights[backIndex]);
          stack.pop_back();
          backIndex = stack.back();
        }
        return maxArea;
    }
};

web前端知识学习笔记-算法篇(1)

下面的内容为排序算法逻辑的摘要，主要目的是方便本人记忆

1. 归并排序（merge sort）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
sort(originalArray) {
     // 当array的规模小于等于1时结束分治
     if (originalArray.length <= 1) {
      return originalArray;
    }
    // 从中间分开左右两个子数组
     const leftArray = originalArray.slice(0, middleIndex);
     const rightArray = originalArray.slice(middleIndex, originalArray.length);
     
     const leftSortedArray = sort(leftArray);
     const rightSortedArray = sort(rightArray);

     // 每次从左右两个已排好序的数组选取出一个最小的元素，加入结果数组
     while (leftArray.length && rightArray.length) {
      if (leftArray[0] < rightArray[0]) {
        minimumElement = leftArray.shift();
      } else {
        minimumElement = rightArray.shift();
      }
      sortedArray.push(minimumElement);
    }
}

2. 快速排序（quick sort）

  1. 非原地
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    sort(array) {
         const pivotElement = array.shift();
         // 根据与基准的大小关系，把元素归入到左，中，右三个子数组
         while (array.length) {
              const currentElement = array.shift();
              if ((currentElement === pivotElement)) {
              centerArray.push(currentElement);
              } else if (currentElement < pivotElement)) {
              leftArray.push(currentElement);
              } else {
              rightArray.push(currentElement);
              }
         }

         // 左右两数组在其内部进行排序
         const leftArraySorted = sort(leftArray);
         const rightArraySorted = sort(rightArray);

         // 合并左中右三个子数组
         leftArraySorted.concat(centerArray, rightArraySorted);
    }
  2. 原地
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    sort(array, inputLowIndex = 0, inputHighIndex = array.length - 1) {
         if (inputLowIndex < inputHighIndex) {
          let partitionIndex = inputLowIndex;
          const pivot = array[highIndex];
          // 把小于最右元素的元素与partitionIndex指向的元素交换位置
          for (let currentIndex = lowIndex; currentIndex < highIndex; currentIndex += 1) {
            if (array[currentIndex] < pivot) {
              swap(partitionIndex, currentIndex);
              partitionIndex += 1;
            }
          }
          swap(partitionIndex, highIndex);
          // 以partitionIndex作为分界点，分开左右范围进行排序
          sort(array, inputLowIndex, partitionIndex - 1);
          sort(array, partitionIndex + 1, inputHighIndex);
        }
    }
    3. 堆排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    // 构建最小堆
    // 每次取出堆顶元素，然后把堆中最后的元素放到堆顶，根据规则，重新建立最小堆
    leftChildIndex(parentIndex) {
         return (2 * parentIndex) + 1;
    }
    rightChildIndex(parentIndex) {
         return (2 * parentIndex) + 2;
    }
    parentIndex(childIndex) {
         return Math.floor((childIndex - 1) / 2);
    }

    // 从最后一个元素开始确认父元素是否小于子元素
    heapifyUp() {
         let currentIndex = heapContainer.length - 1
         while(hasParent(currentIndex) && heapContainer[parentIndex] > heapContainer[currentIndex]) {
              swap(heapContainer, currentIndex, parentIndex);
              currentIndex = parentIndex
         }
    }

    // 从第一个元素开始确认父元素是否小于子元素
    heapifyDown() {
        let currentIndex = 0;
        let nextIndex = null;

        while (this.hasLeftChild(currentIndex)) {
          if (
            this.hasRightChild(currentIndex)
            && rightChild > leftChild)
          ) {
            nextIndex = getRightChildIndex(currentIndex);
          } else {
            nextIndex = getLeftChildIndex(currentIndex);
          }

          if (heapContainer[currentIndex] < heapContainer[nextIndex]) {
            break;
          }

          swap(heapContainer, currentIndex, nextIndex);
          currentIndex = nextIndex;
        }
    }

    add(item) {
         heapContainer.push(item)
         heapifyUp()
    }

    // 从最小堆中取出堆顶，就是poll这个操作
    poll() {
         const item = heapContainer[0]
         heapContainer[0] = heapContainer.pop()
         heapifyDown()
         return item
    }
    奇怪的是根据下面代码来源的资料，heap sort的空间复杂度是O(1)，可是上面的实现方式是需要创建两个数组的，
    按上面的实现应该是O(n)才对。后面经过搜索，得知heap sort实际上是可以原地实现的。实现如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    add() {
      for (let i = 1;i < arr.length;i++) {
        // 从i到0构建**最大堆**
        heapifyUp(i)
      }
    }
    poll() {
      for (let i = arr.length - 1;i >= 0;i++) {
        // 让i与0交换
        swap(i, 0)
        // 调整堆至i - 1处，交换以后的i排除在heapifyDown的操作范围内
        heapifyDown(i - 1)
      }
    }
    // 注意上面的是最大堆，因为这样取出的时候可以把堆顶的这个最大值与末尾的元素进行交换
    // 最后结果能够从小到大排列
    // 上面写的都是伪代码，力求把逻辑简洁地表述出来
    代码来源

web前端知识学习笔记-网络篇(1)

HTTP处于TCP/IP（互联网协议套件）的应用层，是一种无状态的协议。

（我的理解是无状态协议表示，每次请求应答都是独立的，不需要保证是否按顺序收发，不会维护client和server的状态，单次请求应答完成以后自动结束）

一次HTTP操作简化流程

  1. 发送HTTP请求（浏览器输入地址或XHR等方式）
  2. 通过DNS获取请求地址对应的IP地址
  3. 通过TCP/IP，与目标地址建立起TCP连接
  4. TCP连接发送客户端的HTTP请求报文
  5. 客户端通过TCP连接发送HTTP应答报文
  6. TCP连接关闭，如果HTTP请求报头中设置了Connection:keep-alive，则TCP会继续保持连接

值得注意的是keep-alive虽然是通过HTTP的报头设置的，但是实际执行的是在TCP中，所以不与HTTP是无状态的冲突

短连接是无keep-alive，请求完成以后，TCP自动关闭；
长连接则相反。

管线化（with pipelining）是指长连接中客户端无需等待上一次请求完成，再去做第二次请求，非管线化（without pipelining）则需要做这样的等待。
但实际上没有看过非管线化的情况（如果有，还请热心告诉我）

格式示意图

请求报文：

响应报文：

图片来源

常见的响应的状态码

200(OK) 客户端发过来的数据被正常处理

204(Not Content) 正常响应，没有实体

206(Partial Content) 范围请求，返回部分数据，响应报文中由Content-Range指定实体内容

301(Moved Permanently) 永久重定向

302(Found) 临时重定向，重定向后的请求方法可作改变

303(See Other) 重定向后的请求方法变为GET

304(Not Modified) 状态未改变， 配合(If-Match、If-Modified-Since、If-None_Match、If-Range、If-Unmodified-Since)，与HTTP缓存相关

307(Temporary Redirect) 临时重定向，不应改变其请求方法

400(Bad Request) 请求报文语法错误

401(unauthorized) 需要认证

403(Forbidden) 服务器拒绝访问对应的资源

404(Not Found) 服务器上无法找到资源

401跟403不同的地方是，401可能是因为你没有登录，而403表示可能你没有相关的权限，有一次我通过npm发布包，错误提示403，我还错误地想是不是因为我没有登录呢，实际上是我的包名含有private scope，而我没有权限导致的

500(Internal Server Error)服务器故障

503(Service Unavailable) 服务器处于超负载或正在停机维护

从维基百科的配图中，虽然是说明UDP的，但也可以看出在TCP/IP层间传输中，大致存在这样的迭代关系

(n表示层序)

本文内容大部分基于5分钟让你明白HTTP协议https://juejin.im/post/5ad4465d6fb9a028da7d0117

web前端知识学习笔记-JS篇(3)

变量提升与函数提升

1
2
3
4
5
6
7
function outter () {
    return inner;
    function inner () {}
    var inner;
    inner = 9;
}
typeof outter() // 'function';

变量提升和函数提升指的是JS预编译的一个操作。

首先对于var声明的变量，只存在全局作用域和函数作用域，不像let和const还有块作用域。

  1. 变量提升（指var声明的变量）指的是作用域内出现的变量声明会把声明放到作用域的开头
  2. 函数提升是指除了1外的操作，还会把函数提前赋值给变量

根据上面两个规则，上面的代码经预编译会变成如下形式：

1
2
3
4
5
6
function outter () {
    var inner;
    inner = function inner() {}
    return inner;
    inner = 9;
}

web前端知识学习笔记-JS篇(2)

立即执行函数（immediatly invoked function expression）

从题目总结其性质

  1. 1
    2
    3
    4
    5
    6
    7
    8
    const a = 1;
    const b = 30;
    (function a(b) {
         a = 10;
         b = 20;
         console.log(a)
         console.log(b);
    }(10))
    总结：这里会输出a函数定义和20。
  2. 性质一，IIFE的函数名，不会在括号外出现声明，所以不会与const a产生冲突错误。
  3. IIFE的函数名可看作是const，对其再赋值会无效，在严格模式下会报错。

web前端知识学习笔记-JS篇(1)

一条关于setTimeout和promise的执行顺序的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

console.log('1');

setTimeout(function() {
     console.log('2');
     new Promise(function(resolve) {
          console.log('3');
          resolve();
     }).then(function() {
           console.log('4')
})
}, 1)
new Promise(function(resolve) {
     console.log('5');
     resolve();
}).then(function() {
      console.log('6')
})

setTimeout(function() {
     console.log('7');
     new Promise(function(resolve) {
          console.log('8');
          resolve();
     }).then(function() {
      console.log('9')
     })
}, 2)

在浏览器中，其正确顺序是1,5,6,2,3,4,7,8,9
相关知识可以参照Understanding Event Loop, Call Stack, Event & Job Queue in Javascript

简单总结就是

  1. 先执行所有的同步代码，异步代码会放到eventloop执行, setTimeout会放到callback queue, promise会放到job queue
  2. 进入事件循环
  3. 执行job queue的代码，当promise是一个立刻resolve的promise，then产生的promise会在此时放到job queue，由于job queue中有这一步放置的task，所以会继续执行job queue，而不是跳到callback queue中
  4. 再执行callback queue的代码

web前端知识学习笔记-HTML篇(2)

移动端的适配离不开meta标签的viewport设置，比较常见的设置

1
<meta name="viewport" content="width=device-width, initial-scale=1.0" />

属性：

  1. width表示将document内容宽度设为width制定的数值，可填具体数值，如640，或device-width（表示device indepent pixel,简称DIP）
  2. intial-scale, minimum-scale, maximum-scale，表示将可视窗口或者简单理解window.innerWidth，设为DIP / scale，例如当width设为640，而intial-scale设为2.0，那么window.innerWidth === 320，那么窗口内只能看到所有内容的一半。

  3. 关于刘海屏的适配，最开始由ios提出增加一个叫做viewport-fit的属性，一般可用contain 和 cover两个值，
    具体效果可以看下面的示意图:

    1. contain

    contain

    1. cover

    cover

    图片来源

web前端知识学习笔记-HTML篇(1)

语义化，英文为semantics。

根据MDN上的介绍，语义化的优点有

  1. 在SEO中会有较高权重
  2. 方便视觉障碍人士阅读页面
  3. 方便查找有特定意义的标签
  4. 提示开发者生成的数据类型
  5. 语义化仿照与自定义组件的命名

常见的新语义化标签

1
2
3
4
5
6
7
8
9
10
11
12
13
<article>
<aside>
<details> <!--与summary一起使用，点击details显示summary的内容-->
<summary>
<figcaption> <!--图片说明-->
<figure>
<footer>
<header>
<main>
<mark> <!--高亮，默认为黄色背景-->
<nav> <!--导航-->
<section> 
<time> <!--时间-->

web前端知识学习笔记-CSS篇(1)

  1. 一列自适应，一列固定的两列布局实现。
    1
    2
    3
    4
    5
    6
    7
    /* 浮动脱离文档流 */
    .left {
      margin-right: 20px;
    }
    .right {
      float: right;
    }
    1
    2
    3
    4
    5
    <!--注意right要放在left前，float不占用空间的效果只对其后
    的一个元素有效
    -->
    <div class="right"></div>
    <div class="left"></div>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /* 或使用flex */
    .container {
      display: flex;
      height: 100%;
    }
    .left {
      flex: 1;
      height: 100%;
    }
    .right {
      width: 20px;
      height: 100%;
    }
  2. 宽度为相对数值的正方形
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /* 如果相对的是window可用 */
    .square {
      width: 45vw;
      height: 45vw;
    }
    /* 更通用的是使用padding来填充高度，因为padding的相对的是width*/
    .square {
      width: 45%;
      padding-bottom: 100%;
    }