状态机详解（未完待续）

什么是状态机（FSM）？

状态机（Finite State Machine）是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。

字面上讲它是用来管理状态的，状态数量是有限的，并且可以自动执行，即给定一个当前状态与输入，可以明确得到输出状态，当然他不是一个机器，而是一个数学模型。

它有四个概念：

State（状态）：一个状态机至少要包含两个状态，并且状态个数是有限的；
Event（事件）：执行某个操作的触发条件或口令；
Action（动作）：事件发生以后要执行的动作，在我们编程中一般就代指一个函数；
Transition（变换）：从一个状态变到另一个状态。

其他的理解：状态机可归纳为4个要素，即现态、条件、动作、次态。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：

现态：是指当前所处的状态。
条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

状态机能用来做什么

正则表达式引擎

正则表达是引擎是一个典型的状态机的栗子，它分为非确定有限状态自动机NFA(Nondeterministic Finite Automaton)与确定有限状态自动机DFA(Deterministic Finite Automaton)两种，都通通过状态机的概念来实现的。

简单实现一个关于ab|bc的正则匹配：

function match(string) {
  let state = start;
  for (let s of string) {
    console.log('s==>',s);
    state = state(s);
  }
  return state === end;
}

function start(s) {
  if (s === 'a') {
    return foundB1;
  }
  if (s === 'b') {
    return foundB2;
  }
}

function end(s) {
  return end;
}

function foundB1(s) {
  if (s === 'b') {
    return end;
  }
  return start(s);
}

function foundB2(s) {
  if (s === 'c') {
    return end;
  }
  return start(s);
}

const string = 'ab';
console.log(match(string));

KMP算法（Knuth–Morris–Pratt algorithm）

以字符串"BBC ABCDAB ABCDABCDABDE"与搜索词"ABCDABD"进行举例

移动位数 = 已匹配的字符数 - 对应的部分匹配值

Promise

手撸一个Promise的实现：

function Promise(executor) {
    var _this = this
    this.state = 'PENDING'; //状态
    this.value = undefined; //成功结果
    this.reason = undefined; //失败原因

    this.onFulfilled = [];//成功的回调
    this.onRejected = []; //失败的回调
    function resolve(value) {
        if(_this.state === 'PENDING'){
            _this.state = 'FULFILLED'
            _this.value = value
            _this.onFulfilled.forEach(fn => fn(value))
        }
    }
    function reject(reason) {
        if(_this.state === 'PENDING'){
            _this.state = 'REJECTED'
            _this.reason = reason
            _this.onRejected.forEach(fn => fn(reason))
        }
    }
    try {
        executor(resolve, reject);
    } catch (e) {
        reject(e);
    }
}
Promise.prototype.then = function (onFulfilled, onRejected) {
    if(this.state === 'FULFILLED'){
        typeof onFulfilled === 'function' && onFulfilled(this.value)
    }
    if(this.state === 'REJECTED'){
        typeof onRejected === 'function' && onRejected(this.reason)
    }
    if(this.state === 'PENDING'){
        typeof onFulfilled === 'function' && this.onFulfilled.push(onFulfilled)
        typeof onRejected === 'function' && this.onRejected.push(onRejected)
    }
};

HTTP协议

简单封装一个http请求的响应解析器：

const net = require('net');
const images = require('images');
const parser = require('./parser');
const render = require('./render');

class Request {
  constructor(options) {
    this.method = options.method || 'GET';
    this.host = options.host;
    this.port = options.port || 80;
    this.path = options.path || '/';
    this.body = options.body || {};
    this.headers = options.headers || {};
    if (!this.headers['Content-Type']) {
      this.headers['Content-Type'] = 'application/x-www-form-urlencoded';
    }
    if (this.headers['Content-Type'] == 'application/json') {
      this.bodyText = JSON.stringify(this.body);
    } else if (this.headers['Content-Type'] === 'application/x-www-form-urlencoded') {
      this.bodyText = Object.keys(this.body).map(key => `${key}=${encodeURIComponent(this.body[key])}`).join('&');
    }
    this.headers['Content-Length'] = this.bodyText.length;
  }

  send(connection) {
    return new Promise((resolve, reject) => {
      // do something
      let parser = new ResponseParser();
      if (connection) {
        connection.write(this.toString());
      } else {
        connection = net.createConnection({
          host: this.host,
          port: this.port
        }, () => {
          connection.write(this.toString());
        });
      }

      connection.on('data', data => {
        parser.receive(data.toString());
        console.log(parser.isFinished,'isFinished');
        if (parser.isFinished) {
          resolve(parser.response);
          connection.end();
        }
      });

      connection.on('error', err => {
        reject(err);
        connection.end();
      });
    });
  }

  toString() {
    return `${this.method} ${this.path} HTTP/1.1\r
${Object.keys(this.headers).map(key => `${key}: ${this.headers[key]}`).join('\r\n')}\r
\r
${this.bodyText}`;
  }
};

class ResponseParser {
  constructor() {
    this.WAITING_STATUS_LINE = 0;
    this.WAITING_STATUS_LINE_END = 1;
    this.WAITING_HEADER_NAME = 2;
    this.WAITING_HEADER_SPACE = 3;
    this.WAITING_HEADER_VALUE = 4;
    this.WAITING_HEADER_LINE_END = 5;
    this.WAITING_HEADER_BLOCK_END = 6;
    this.WAITING_BODY = 7;

    this.current = this.WAITING_STATUS_LINE;
    this.statusLine = '';
    this.headers = {};
    this.headerName = '';
    this.headerValue = '';
    this.bodyParser = null;
  }

  get isFinished() {
    return this.bodyParser && this.bodyParser.isFinished;
  }

  get response() {
    this.statusLine.match(/HTTP\/1.1 ([0-9]+) ([\s\S]+)/);
    return {
      statusCode: RegExp.$1,
      statusText: RegExp.$2,
      headers: this.headers,
      body: this.bodyParser.content.join('')
    }
  }

  receive(string) {
    for (let i = 0; i < string.length; i++) {
      this.receiveChar(string.charAt(i));
    }
  }

  receiveChar(char) {
    if (this.current === this.WAITING_STATUS_LINE) {
      if (char === '\r') {
        this.current = this.WAITING_STATUS_LINE_END;
      } else {
        this.statusLine += char;
      }
    } else if (this.current === this.WAITING_STATUS_LINE_END) {
      if (char === '\n') {
        this.current = this.WAITING_HEADER_NAME;
      }
    } else if (this.current === this.WAITING_HEADER_NAME) {
      if (char === ':') {
        this.current = this.WAITING_HEADER_SPACE;
      } else if (char === '\r') {
        this.current = this.WAITING_HEADER_BLOCK_END;
        if (this.headers['Transfer-Encoding'] === 'chunked') {
          this.bodyParser = new TrunkedBodyParser();
        }
      } else {
        this.headerName += char;
      }
    } else if (this.current === this.WAITING_HEADER_SPACE) {
      if (char === ' ') {
        this.current = this.WAITING_HEADER_VALUE;
      }
    } else if (this.current === this.WAITING_HEADER_VALUE) {
      if (char === '\r') {
        this.current = this.WAITING_HEADER_LINE_END;
        this.headers[this.headerName] = this.headerValue;
        this.headerName = '';
        this.headerValue = '';
      } else {
        this.headerValue += char;
      }
    } else if (this.current === this.WAITING_HEADER_LINE_END) {
      if (char === '\n') {
        this.current = this.WAITING_HEADER_NAME;
      }
    } else if (this.current === this.WAITING_HEADER_BLOCK_END) {
      if (char === '\n') {
        this.current = this.WAITING_BODY;
      }
    } else if (this.current === this.WAITING_BODY) {
      this.bodyParser.receiveChar(char);
    }
  }
}

class TrunkedBodyParser {
  constructor() {
    this.WAITING_LENGTH = 0;
    this.WAITING_LENGTH_LINE_END = 1;
    this.READING_TRUNK = 2;
    this.WAITING_NEW_LINE = 3;
    this.WAITING_NEW_LINE_END = 4;
    this.length = 0;
    this.content = [];
    this.isFinished = false;
    this.current = this.WAITING_LENGTH;
  }

  receiveChar(char) {
    if (this.current === this.WAITING_LENGTH) {
      if (char === '\r') {
        if (this.length === 0) {
          this.isFinished = true;
        }
        this.current = this.WAITING_LENGTH_LINE_END;
      } else {
        this.length *= 16;
        this.length += parseInt(char, 16);
      }
    } else if (this.current === this.WAITING_LENGTH_LINE_END) {
      if (char === '\n') {
        this.current = this.READING_TRUNK;
      }
    } else if (this.current === this.READING_TRUNK) {
      this.content.push(char);
      this.length--;
      if (this.length === 0) {
        this.current = this.WAITING_NEW_LINE;
      }
    } else if (this.current === this.WAITING_NEW_LINE) {
      if (char === '\r') {
        this.current = this.WAITING_NEW_LINE_END;
      }
    } else if (this.current === this.WAITING_NEW_LINE_END) {
      if (char === '\n') {
        this.current = this.WAITING_LENGTH;
      }
    }
  }
}

void async function() {
  let request = new Request({
    method: 'POST',
    host: '127.0.0.1',
    port: 8088,
    path: '/',
    headers: {
      ['X-Foo2']: 'customed'
    },
    body: {
      name: 'test'
    }
  });

  let response = await request.send();

  let dom = parser.parseHTML(response.body);

  let viewport = images(800, 600);

  render(viewport, dom.children[0].children[3].children[1].children[3]);

  viewport.save("viewport.jpg");

  console.log(JSON.stringify(dom, null, '    '), 'dom');
}();

HTML解析

在html标准里边，html的词法描述就是按照状态机的概念来进行描述的，详细;

设计模式--状态模式

允许一个对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类。其别名为状态对象(Objects for States)，状态模式是一种对象行为型模式。

设计模式中有个状态模式，还有一个策略模式，两者有点相似，又有些不同，它们的相同点是，都有一个上下文、一些策略类或者状态类，上下文把请求委托给这些类来执行。它们之间的区别是策略模式中的各个策略类之间是平等又平行的，它们之间没有任何关系，所以客户必须熟知这些策略类的作用，以便客户自己可以随时主动切换算法。但是在状态模式中，状态和状态对应的行为早已被封装好，状态之间的切换也早就被规定，“改变行为”这件事发生在状态模式的内部，对于客户来说，不需要了解这些细节。

讲的多都不如直接看代码，那么我们通过栗子来理解一下状态模式的应用：

一个比较常见的场景栗子电灯只有一个开关，但是它的表现是：第一次按下打开弱光，第二次按下打开强光，第三次才是关闭电灯。

未使用状态模式：

class Light {
  construct () {
    this.state = 'off'
    this.button = null
  }

  // 创建一个button负责控制电灯的开关
  init () {
    const button = document.createElement('button')
    this.button = document.body.appendChild(button)
    this.button.innerHTML = '开关'

    this.button.onclick = () => {
      this.buttonWasPressed()
    }
  }

  buttonWasPressed () {
    if (this.state === 'off') {
        console.log('弱光')
        this.state = 'weak'
    } else if (this.state === 'weak') {
        console.log('强光')
        this.state = 'strong'
    } else if (this.state === 'strong') {
        console.log('关灯')
        this.state = 'off'
    }
  }
}

const light = new Light()
light.init()

使用状态模式的代码：

class OffLightState {
  construct (light) {
    this.light = light
  }

  buttonWasPressed () {
    console.log('弱光')
    this.light.setState(this.light.weakLightState)
  }
}

class WeakLightState {
  construct (light) {
    this.light = light
  }

  buttonWasPressed () {
    console.log('强光')
    this.light.setState(this.light.strongLightState)
  }
}

class StrongLightState {
  construct (light) {
    this.light = light
  }

  buttonWasPressed () {
    console.log('关灯')
    this.light.setState(this.light.offLightState)
  }
}

// light类
class Light {
  construct () {
    this.offLightState = new OffLightState(this)
    this.weakLightState = new WeakLightState(this)
    this.strongLightState = new StrongLightState(this)

    this.currentState = this.offLightState // 初始化电灯状态
    this.button = null
  }

  init () {
    const button = document.createElement('button')
    this.button = document.body.appendChild(button)
    this.button.innerHTML = '开关'

    this.button.onclick = () => {
      this.currentState.buttonWasPressed()
    }
  }

  setState (newState) {
    this.currentState = newState
  }
}

const light = new Light()
light.init()

此外，状态机的概念还用于语言的词法分析，语法分析，网络协议，游戏设计，客服机器人等各个方面，是我们编程中一个很重要的概念

推荐工具：

Javascript Finite State Machine--一个功能强大的状态机函数库

参考链接：

kd-cloud-web / Blog