浏览器工作原理

---

浏览器工作原理概论

• URL -> HTML -> DOM -> DOM with CSS -> DOM with position -> Bitmap

1. 解析 HTML 和 CSS 代码；
2. 创建渲染上下文；
3. 应用 CSS 样式；（CSS computing）
4. 布局阶段；（layout）
5. 绘制阶段；（render）

• 硬件加速；分层渲染；离屏渲染；

• 主要渲染技术：Skia / CSSOM / WebGL

---

有限状态机

function match(string) {
  let state = start;
  for (const c of string) {
    state = state(c);
  }
  return state === end;
}

function start(token) {
  if (token === "a") {
    return foundA;
  } else {
    return start;
  }
}

// trap function
function end(token) { 
  return end;
}

function foundA(token) {
  if (token === "b") {
    return foundB;
  } else {
    // token传入start函数，reConsume
    return start(token); 
  }
}
...

扩展：KMP算法

https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

function kmp(text, pattern) {
  const next = getNext(pattern);
  let i = 0,
    j = 0;
  const result = [];

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        result.push(i - j);
        j = next[j - 1];
      }
    } else {
      if (j === 0) {
        i++;
      } else {
        j = next[j - 1];
      }
    }
  }

  return result;
}

function getNext(pattern) {
  const next = [];
  next[0] = 0;

  for (let i = 1; i < pattern.length; i++) {
    let j = next[i - 1];

    while (j > 0 && pattern[i] !== pattern[j]) {
      j = next[j - 1];
    }

    if (pattern[i] === pattern[j]) {
      next[i] = j + 1;
    } else {
      next[i] = 0;
    }
  }

  return next;
}

程序员如何写好一份简历