解析模板字符串

parseHTML

parseHTML(html, options)函数的作用是循环解析传入的html字符串,单次循环可以解析出元素的开始标签(也称为开放标签)或结束标签(也称为闭合标签)或文本或注释中的一种,进而调用options.start/end/chars/comment回调函数以分别处理这些解析出的内容。每循环一次,html字符串就被解析出一段内容,就调用一次回调函数,经过多次循环,直到html字符串全部解析完成。

解析过程主要是利用正则表达式做正则匹配,从html字符串的第一个字符开始,每识别出一段文本属于那种类型,就调用options中对应的方法传递给parser做对应的处理。先简单介绍options里各个方法的作用:

  • options.start:处理开始标签及特性,包括创建 AST 元素,处理指令、事件、特性等等,对于非一元标签,还会推入栈中
  • optuons.end:处理结束标签,做一些清理工作,对于非一元标签,会将标签退出栈中
  • options.chars:处理文本内容
  • options.comment:处理注释内容

那么,我们是如何从庞大而冗长的html字符串里,解析出开始标签/结束标签/特性/文本/注释的呢?

拿到html字符串,只要字符串不为空,就不断地进行如下的循环。循环体里,html字符串的开头部分每匹配一次,html字符串都将丢弃匹配好的部分,保留未匹配的部分,直到html字符串完全匹配。

匹配主要分为两大部分:

  1. 首次匹配 || 上一次匹配的lastTag不是纯文本元素标签(比如script,style,textarea
    • html的第一个字符是<
      • 匹配到注释:获取完整的注释字符串及注释结尾位置,调用options.comment处理,丢弃注释部分的字符串,continue继续处理注释之后的字符串
      • 匹配到 IE 条件注释:获取条件注释的结尾位置,丢弃条件注释部分的字符串,continue继续处理条件注释之后的字符串
      • 匹配到 Doctype:获取 Doctype 的结尾位置,丢弃 Doctype 字符串,continue继续处理 Doctype 之后的字符串
      • 匹配到结束标签:获取完整的结束标签字符串,做如下处理后,continue继续处理结束标签之后的字符串
        • 查找stack栈里最后一个同名的标签
          • 若能找到
            • 遍历栈尾到该标签之间的所有标签(这些标签都没有闭合),发出警告
            • 调用options.end并将这些没有结束标签的标签和结束标签提交给外界处理
            • 重置stack栈的大小,即删除stack里从栈尾到(包括)该标签的所有标签
          • 若找不到,处理结束标签为br/p的特殊情况
      • 匹配到开始标签,做如下处理后,continue继续处理开始标签之后的字符串
        • 解析开始标签,提取出特性字符串,分辨出是否是一元标签
        • 处理开始标签
          • 处理某些特殊情况
          • 将特性字符串处理成对象形式
          • 对于非一元标签,推入栈中
          • 调用options.start(),将开始标签相关信息交给外界处理(外界创建 AST 元素,处理指令、事件、特性等等)
    • 若上一步没匹配到或html的第一个字符不是<,匹配文本,调用options.char将文本交给外界处理
  2. 非首次匹配 && 上一次匹配的lastTag是纯文本元素标签(比如script,style,textarea
    • 将标签内包含的<!\-- --><![CDATA[]]>移除
    • 调用options.chars()将标签内的文本提交给外界处理
    • 做与“匹配到结束标签”相同的处理

示例

如下先给出一个简单示例,说明parseHTML是如何解析 HTML 的。

假设组件的模板是下面这样,且假设传入的options.shouldKeepCommenttrue

<div class="container">
  <!--这里是注释内容-->
  <p v-if="isRoot" style="font-size: 12px">插值内容<br> {{ chazhi }}</p>
</div>
1
2
3
4

为了让上面html字符串里节点之间不易见的空格和换行符更加明显,我们用*来表示空格,用#来表示换行符\n

<div class="container">#
**<!--这里是注释内容-->#
**<p v-if="isRoot" style="font-size: 12px">插值内容<br>{{ chazhi }}</p>#
</div>
1
2
3
4
  • 第一次循环,匹配到开始标签,<div class="container">
    • 解析开始标签
      • tagdiv
      • attrs[ 'class="container"' ]
      • unarySlashfalse,即不是一元标签
    • 处理标签
      • attrs特性字符串处理为[ { name: 'class', value: 'container' } ]
      • 将开始标签推入stack
      • 调用options.start(tagName, attrs, unary, match.start, match.end)
        • tagName: 'div'
        • attrs: [ { name: 'class', value: 'container' } ]
        • unary: false
        • match.start: 0
        • match.end: 23

第一次循环后,html字符串和stack变成了下面这样:(空格已经用*代替)

                       #
**<!--这里是注释内容-->#
**<p v-if="isRoot" style="font-size: 12px">插值内容<br>{{ chazhi }}</p>#
</div>
1
2
3
4
stack = [
  { tag: 'div', lowerCasedTag: 'div', attrs: [ { name: 'class', value: 'container' } ] }
]
1
2
3
  • 第二次循环,匹配到文本#**,即<div class="container"><!-- 这里是注释内容 -->之间的内容,调用options.chars('#**')

第二次循环后,html字符串变成了下面这样:

  <!--这里是注释内容-->#
**<p v-if="isRoot" style="font-size: 12px">插值内容<br>{{ chazhi }}</p>#
</div>
1
2
3
  • 第三次循环,匹配到注释节点,<!--这里是注释内容-->,调用options.comment('这里是注释内容')

第三次循环后,html字符串变成了下面这样:

                     #
**<p v-if="isRoot" style="font-size: 12px">插值内容<br>{{ chazhi }}</p>#
</div>
1
2
3
  • 第四次循环,匹配到文本#**,即<!--这里是注释内容--><p...之间的内容

第四次循环后,html字符串变成了下面这样:

  <p v-if="isRoot" style="font-size: 12px">插值内容<br>{{ chazhi }}</p>#
</div>
1
2
  • 第五次循环,匹配到开始标签,<p v-if="isRoot" style="font-size: 12px">
    • 解析开始标签
      • tagp
      • attrs[ 'v-if="isRoot"', 'style="font-size: 12px"' ]
      • unarySlashfalse,即不是一元标签
    • 处理标签
      • attrs特性字符串处理为[ { name: 'v-if', value: 'isRoot' }, { name: 'style', value: 'font-size: 12px' } ]
      • 将开始标签推入stack
      • 调用options.start(tagName, attrs, unary, match.start, match.end)
        • tagName: 'p'
        • attrs: [ { name: 'v-if', value: 'isRoot' }, { name: 'style', value: 'font-size: 12px' } ]
        • unary: false
        • match.start: 43
        • match.end: 84

第五次循环后,html字符串和stack变成了下面这样:

                                           插值内容<br>{{ chazhi }}</p>#
</div>
1
2
stack = [
  { tag: 'div', lowerCasedTag: 'div', attrs: [ { name: 'class', value: 'container' } ] },
  { tag: 'p', lowerCasedTag: 'p', attrs: [ { name: 'v-if', value: 'isRoot' }, { name: 'style', value: 'font-size: 12px' } ] }
]
1
2
3
4
  • 第六次循环,匹配到文本插值内容
                                                  <br>{{ chazhi }}</p>#
</div>
1
2
  • 第七次循环,匹配到开始标签,<br>
    • 解析开始标签
      • tagbr
      • attrs[]
      • unarySlashtrue,是一元标签
    • 处理标签
      • attrs特性字符串处理为[]
      • 调用options.start(tagName, attrs, unary, match.start, match.end)
        • tagName: 'br'
        • attrs: []
        • unary: true
        • match.start: 88
        • match.end: 92
                                                      {{ chazhi }}</p>#
</div>
1
2
  • 第八循环,匹配到文本
                                                                  </p>#
</div>
1
2
  • 第九循环,匹配到结束标签,</p>
    • stack栈里找到了p标签
    • 调用options.end()
    • 删除stack栈里p标签~最后一个标签
                                                                      #
</div>
1
2
stack = [
  { tag: 'div', lowerCasedTag: 'div', attrs: [ { name: 'class', value: 'container' } ] }
]
1
2
3
  • 第十循环,匹配到文本#
</div>
1
  • 第十一循环,匹配到结束标签,</div>
    • stack栈里找到了div标签
    • 调用options.end()
    • 删除stack栈里div标签~最后一个标签

至此,html解析完成,stack栈也为[]了。

上面的描述仅仅说明了大概的过程,省略了很多细节,更加详细的内容需要阅读源码。

源码

/**
 * Not type-checking this file because it's mostly vendor code.
 */

/*!
 * HTML Parser By John Resig (ejohn.org)
 * Modified by Juriy "kangax" Zaytsev
 * Original code by Erik Arvidsson, Mozilla Public License
 * http://erik.eae.net/simplehtmlparser/simplehtmlparser.js
 */

import { makeMap, no } from 'shared/util'
import { isNonPhrasingTag } from 'web/compiler/util'

// Regular Expressions for parsing tags and attributes
/**
 * attribute 正则分析
 *
 * /
 * ^\s*([^\s"'<>\/=]+)  特性的名称
 *  (?:
 *    \s*
 *    (=)  特性的等号
 *    \s*
 *    (?:
 *      "([^"]*)"+|     用双引号""包含起来的特性值
 *      '([^']*)'+|     用单引号''包含起来的特性值
 *      ([^\s"'=<>`]+)  不用单双引号包含起来的特性值
 *    )
 *  )?
 * /
 *
 */
const attribute = /^\s*([^\s"'<>\/=]+)(?:\s*(=)\s*(?:"([^"]*)"+|'([^']*)'+|([^\s"'=<>`]+)))?/
// could use https://www.w3.org/TR/1999/REC-xml-names-19990114/#NT-QName
// but for Vue templates we can enforce a simple charset
const ncname = '[a-zA-Z_][\\w\\-\\.]*'
const qnameCapture = `((?:${ncname}\\:)?${ncname})`
const startTagOpen = new RegExp(`^<${qnameCapture}`)
const startTagClose = /^\s*(\/?)>/
const endTag = new RegExp(`^<\\/${qnameCapture}[^>]*>`)
const doctype = /^<!DOCTYPE [^>]+>/i
// #7298: escape - to avoid being pased as HTML comment when inlined in page
const comment = /^<!\--/
const conditionalComment = /^<!\[/

let IS_REGEX_CAPTURING_BROKEN = false
'x'.replace(/x(.)?/g, function (m, g) {
  IS_REGEX_CAPTURING_BROKEN = g === ''
})

// Special Elements (can contain anything)
export const isPlainTextElement = makeMap('script,style,textarea', true)
const reCache = {}

const decodingMap = {
  '&lt;': '<',
  '&gt;': '>',
  '&quot;': '"',
  '&amp;': '&',
  '&#10;': '\n',
  '&#9;': '\t'
}
const encodedAttr = /&(?:lt|gt|quot|amp);/g
const encodedAttrWithNewLines = /&(?:lt|gt|quot|amp|#10|#9);/g

// #5992
const isIgnoreNewlineTag = makeMap('pre,textarea', true)
const shouldIgnoreFirstNewline = (tag, html) => tag && isIgnoreNewlineTag(tag) && html[0] === '\n'

/**
 * 解码特性的值里的编码的字符
 * @param {*} value 特性的值
 * @param {*} shouldDecodeNewlines 是否需要解码
 *
 * TODO: 这是为了防止 XSS 攻击吗?
 */
function decodeAttr (value, shouldDecodeNewlines) {
  const re = shouldDecodeNewlines ? encodedAttrWithNewLines : encodedAttr
  return value.replace(re, match => decodingMap[match])
}

/**
 * 解析 html 模板
 * @param {String} html 模板字符串
 * @param {Object} options 选项对象
 */
export function parseHTML (html, options) {
  const stack = []
  const expectHTML = options.expectHTML
  const isUnaryTag = options.isUnaryTag || no
  const canBeLeftOpenTag = options.canBeLeftOpenTag || no
  let index = 0
  // lastTag 是上一个已经处理完开始标签,但是还没处理结束标签的元素
  let last, lastTag
  while (html) {
    last = html
    // Make sure we're not in a plaintext content element like script/style
    if (!lastTag || !isPlainTextElement(lastTag)) {
      let textEnd = html.indexOf('<')
      // 匹配注释、IE条件注释、doctype、开始标签、结束标签
      if (textEnd === 0) {
        // Comment:
        // html 以 正常注释文本 开头:去掉注释继续下一次循环
        // comment = /^<!\--/
        if (comment.test(html)) {
          const commentEnd = html.indexOf('-->')

          if (commentEnd >= 0) {
            if (options.shouldKeepComment) {
              // 处理 注释内容
              options.comment(html.substring(4, commentEnd))
            }
            advance(commentEnd + 3)
            continue
          }
        }

        // http://en.wikipedia.org/wiki/Conditional_comment#Downlevel-revealed_conditional_comment
        // html 以 IE条件注释文本 开头:去掉注释继续下一次循环
        // conditionalComment = /^<!\[/
        if (conditionalComment.test(html)) {
          const conditionalEnd = html.indexOf(']>')

          if (conditionalEnd >= 0) {
            advance(conditionalEnd + 2)
            continue
          }
        }

        // Doctype:
        // html 以 Doctype 开头:去掉 Doctype 继续下一次循环
        // doctype = /^<!DOCTYPE [^>]+>/i
        const doctypeMatch = html.match(doctype)
        if (doctypeMatch) {
          advance(doctypeMatch[0].length)
          continue
        }

        // End tag:
        // html 以结束标签开头:去掉结束标签继续下一次循环,并处理结束标签
        const endTagMatch = html.match(endTag)
        // ncname = '[a-zA-Z_][\\w\\-\\.]*'
        // qnameCapture = `((?:${ncname}\\:)?${ncname})`
        // endTag = new RegExp(`^<\\/${qnameCapture}[^>]*>`)
        if (endTagMatch) {
          const curIndex = index
          advance(endTagMatch[0].length)
          parseEndTag(endTagMatch[1], curIndex, index)
          continue
        }

        // Start tag:
        // html 以开始标签开头:
        const startTagMatch = parseStartTag()
        if (startTagMatch) {
          handleStartTag(startTagMatch)
          if (shouldIgnoreFirstNewline(lastTag, html)) {
            // pre、textarea 标签内,忽略首个 \n
            advance(1)
          }
          continue
        }
      }

      // 若是不能匹配,则获取文本
      let text, rest, next
      if (textEnd >= 0) {
        rest = html.slice(textEnd)

        // 查找到第一个能解析出来的 <,从 0 ~ 这个能解析出来的 < 字符之间的内容都是文本(有可能找不到能解析的 <)
        while (
          !endTag.test(rest) &&
          !startTagOpen.test(rest) &&
          !comment.test(rest) &&
          !conditionalComment.test(rest)
        ) {
          // < in plain text, be forgiving and treat it as text
          // 若 html 里只有一个 <
          next = rest.indexOf('<', 1)
          if (next < 0) break

          // 若 html 里有至少两个 <
          textEnd += next
          rest = html.slice(textEnd)
        }
        // while 循环结束时,textEnd 为 html 里最后一个不能解析为 结束标签/开始标签的前部/注释标签/条件注释标签 的 < 的位置
        // 即 textEnd 之前的部分都将成为文本
        text = html.substring(0, textEnd)
        advance(textEnd)
      }

      // 若 html 里没有 <,则整个 html 都为文本
      if (textEnd < 0) {
        text = html
        html = ''
      }

      // 调用 options.chars 处理文本内容
      if (options.chars && text) {
        options.chars(text)
      }
    } else {
      // lastTag 是 script,style,textarea 时,会走到这里
      // 即,接下来处理 script,style,textarea 内的内容(包括闭合标签)
      let endTagLength = 0
      const stackedTag = lastTag.toLowerCase()
      const reStackedTag = reCache[stackedTag] || (reCache[stackedTag] = new RegExp('([\\s\\S]*?)(</' + stackedTag + '[^>]*>)', 'i'))
      const rest = html.replace(reStackedTag, function (all, text, endTag) {
        endTagLength = endTag.length
        if (!isPlainTextElement(stackedTag) && stackedTag !== 'noscript') {
          text = text
            // <![CDATA[这里是不被 HTML 解析的内容]]>
            // <!\--这里是不被 HTML 解析的内容-->
            // 上面两种情况里包含的内容不会被 HMLT 解析,其中可能会包含 js 代码,因此需要将 <!\-- -->、<![CDATA[]]> 移除
            .replace(/<!\--([\s\S]*?)-->/g, '$1') // #7298
            .replace(/<!\[CDATA\[([\s\S]*?)]]>/g, '$1')
        }
        if (shouldIgnoreFirstNewline(stackedTag, text)) {
          // pre、textarea 标签内,忽略首个 \n
          text = text.slice(1)
        }
        if (options.chars) {
          options.chars(text)
        }
        return ''
      })
      index += html.length - rest.length
      html = rest
      // 解析结束标签
      parseEndTag(stackedTag, index - endTagLength, index)
    }

    if (html === last) {
      // 若该轮循环 html 没有发生如何变化(即没有解析出任何内容),发出警告
      options.chars && options.chars(html)
      if (process.env.NODE_ENV !== 'production' && !stack.length && options.warn) {
        options.warn(`Mal-formatted tag at end of template: "${html}"`)
      }
      break
    }
  }

  // Clean up any remaining tags
  parseEndTag()

  /**
   * 截取 html 模板,并设置当前 html 模板的开始位置位于最初 html 模板里的位置
   */
  function advance (n) {
    index += n
    // 保留 n ~ html.length 的字符串
    html = html.substring(n)
  }

  /**
   * 解析开始标签,返回结果对象
   * {
   *   tagName, 标签名
   *   attrs, 特性匹配数组
   *   start, 开始标签在 template 里的开始位置
   *   end, (可选)开始标签在 template 里的结束位置
   *   unarySlash, 一元标签的 /
   * }
   */
  function parseStartTag () {
    // ncname = '[a-zA-Z_][\\w\\-\\.]*'
    // qnameCapture = `((?:${ncname}\\:)?${ncname})`
    // startTagOpen = new RegExp(`^<${qnameCapture}`)
    const start = html.match(startTagOpen)
    if (start) {
      const match = {
        tagName: start[1],
        // 保存特性匹配结果数组,其元素是个 Array.prototype.match() 的匹配结果数组
        attrs: [],
        start: index
      }
      advance(start[0].length)
      let end, attr
      // 没匹配到开始标签的关闭 && 匹配到特性
      // startTagClose = /^\s*(\/?)>/
      while (!(end = html.match(startTagClose)) && (attr = html.match(attribute))) {
        advance(attr[0].length)
        match.attrs.push(attr)
      }
      if (end) {
        // 一元标签的 slash
        match.unarySlash = end[1]
        advance(end[0].length)
        match.end = index
        return match
      }
    }
  }

  /**
   * 处理开始标签
   * @param {Object} match 开始标签的正则匹配结果
   *   {String} tagName 标签名
   *   {Array} attrs 特性数组,其元素为特性的 Array.prototype.match 的匹配结果数组
   *   {Number} start 开始标签的位置
   *   {Number} end 可选,开始标签的位置(> 的下一位置)
   *   {String} unarySlash 可选,一元开始标签的 /
   *
   * 所做的处理有:
   * 1. 某些情况下,需要先结束上一标签
   * 2. 将特性处理成对象形式,如 attrs = [{ name, value }, ...]
   * 3. 对于非一元标签,将其推入 stack 栈中,更新 lastTag
   * 4. 调用 options.start 函数,创建 AST 元素,处理指令、事件、特性等等
   */
  function handleStartTag (match) {
    const tagName = match.tagName
    const unarySlash = match.unarySlash

    // 某些情况下,先结束上一标签
    if (expectHTML) {
      if (lastTag === 'p' && isNonPhrasingTag(tagName)) {
        // 对于不能出现在 p 标签内的元素
        // 先结束解析上一个 p 标签
        parseEndTag(lastTag)
      }
      if (canBeLeftOpenTag(tagName) && lastTag === tagName) {
        // 当前标签是可以不关闭的,且上一个元素是同一标签,比如  <li> 111 <li> 222
        // 则先将上一标签关闭
        parseEndTag(tagName)
      }
    }

    const unary = isUnaryTag(tagName) || !!unarySlash

    const l = match.attrs.length
    const attrs = new Array(l)
    /**
     * attribute 正则分析
     *
     * /
     * ^\s*([^\s"'<>\/=]+)  特性的名称
     *  (?:
     *    \s*
     *    (=)  特性的等号
     *    \s*
     *    (?:
     *      "([^"]*)"+|     用双引号""包含起来的特性值    args[3]
     *      '([^']*)'+|     用单引号''包含起来的特性值    args[4]
     *      ([^\s"'=<>`]+)  不用单双引号包含起来的特性值   args[5]
     *    )
     *  )?
     * /
     *
     */
    // 将特性处理成对象形式,{ name, value }
    for (let i = 0; i < l; i++) {
      const args = match.attrs[i]
      // hackish work around FF bug https://bugzilla.mozilla.org/show_bug.cgi?id=369778
      if (IS_REGEX_CAPTURING_BROKEN && args[0].indexOf('""') === -1) {
        if (args[3] === '') { delete args[3] }
        if (args[4] === '') { delete args[4] }
        if (args[5] === '') { delete args[5] }
      }
      // 特性的值
      const value = args[3] || args[4] || args[5] || ''
      const shouldDecodeNewlines = tagName === 'a' && args[1] === 'href'
        ? options.shouldDecodeNewlinesForHref
        : options.shouldDecodeNewlines
      attrs[i] = {
        name: args[1],
        value: decodeAttr(value, shouldDecodeNewlines)
      }
    }

    // 非一元标签,推入栈中(等待结束标签),更新 lastTag
    if (!unary) {
      stack.push({ tag: tagName, lowerCasedTag: tagName.toLowerCase(), attrs: attrs })
      lastTag = tagName
    }

    // 处理开始标签:创建 AST 元素,处理指令、事件、特性等等
    if (options.start) {
      options.start(tagName, attrs, unary, match.start, match.end)
    }
  }

  /**
   * 解析结束标签:若堆栈里有没闭合的标签,发出警告;针对 br 和 p 标签做一些异常处理
   * @param {*} tagName 结束标签名
   * @param {*} start 结束标签的开始位置(即 </xxx> 的 < 的位置)
   * @param {*} end 结束标签的结束位置(即 </xxx> 的 > 的下一位置)
   */
  function parseEndTag (tagName, start, end) {
    let pos, lowerCasedTagName
    if (start == null) start = index
    if (end == null) end = index

    if (tagName) {
      lowerCasedTagName = tagName.toLowerCase()
    }

    // Find the closest opened tag of the same type
    // 查找 stack 栈里最后进栈的相同标签,若找不到相同标签,pos 为 -1
    if (tagName) {
      for (pos = stack.length - 1; pos >= 0; pos--) {
        if (stack[pos].lowerCasedTag === lowerCasedTagName) {
          break
        }
      }
    } else {
      // If no tag name is provided, clean shop
      pos = 0
    }

    if (pos >= 0) {
      // Close all the open elements, up the stack
      // 对于没闭合的标签,发出警告,并调用 options.end 闭合
      for (let i = stack.length - 1; i >= pos; i--) {
        if (process.env.NODE_ENV !== 'production' &&
          (i > pos || !tagName) &&
          options.warn
        ) {
          options.warn(
            `tag <${stack[i].tag}> has no matching end tag.`
          )
        }
        if (options.end) {
          options.end(stack[i].tag, start, end)
        }
      }

      // Remove the open elements from the stack
      stack.length = pos

      // 标签闭合后,更新 lastTag
      lastTag = pos && stack[pos - 1].tag
    } else if (lowerCasedTagName === 'br') {
      // 没找到对应的开始标签 && </br>:将 </br> 转换成 <br>
      // PS: <br></br> 这种使用是错误的,经过此处的处理,将变成 <br><br>
      if (options.start) {
        options.start(tagName, [], true, start, end)
      }
    } else if (lowerCasedTagName === 'p') {
      // 没找到对应的开始标签 && </p>:添加开始标签
      if (options.start) {
        options.start(tagName, [], false, start, end)
      }
      if (options.end) {
        options.end(tagName, start, end)
      }
    }
  }
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449