routerMatcher #

export function createRouterMatcher(
  routes: RouteRecordRaw[],
  globalOptions: PathParserOptions
): RouterMatcher {
  // ...
  return { addRoute, resolve, removeRoute, getRoutes, getRecordMatcher }
}

const matchers: RouteRecordMatcher[] = []
const matcherMap = new Map<RouteRecordName, RouteRecordMatcher>()
globalOptions = mergeOptions(
  { strict: false, end: true, sensitive: false } as PathParserOptions,
  globalOptions
)

function mergeOptions<T>(defaults: T, partialOptions: Partial<T>): T {
  const options = {} as T
  for (const key in defaults) {
    options[key] = key in partialOptions ? partialOptions[key]! : defaults[key]
  }

  return options
}

// add initial routes
routes.forEach(route => addRoute(route))

return { addRoute, resolve, removeRoute, getRoutes, getRecordMatcher }

function addRoute(
  record: RouteRecordRaw,
  parent?: RouteRecordMatcher,
  originalRecord?: RouteRecordMatcher
) {
  // used later on to remove by name
  const isRootAdd = !originalRecord
  // 标准化化路由记录
  const mainNormalizedRecord = normalizeRouteRecord(record)
  // aliasOf表示此记录是否是另一个记录的别名
  mainNormalizedRecord.aliasOf = originalRecord && originalRecord.record
  const options: PathParserOptions = mergeOptions(globalOptions, record)
  // 声明一个记录的数组用来处理别名
  const normalizedRecords: typeof mainNormalizedRecord[] = [
    mainNormalizedRecord,
  ]
  // 如果record设置了别名
  if ('alias' in record) {
    // 别名数组
    const aliases =
      typeof record.alias === 'string' ? [record.alias] : record.alias!
    // 遍历别名数组，并根据别名创建记录存储到normalizedRecords中
    for (const alias of aliases) {
      normalizedRecords.push(
        assign({}, mainNormalizedRecord, {
          components: originalRecord
            ? originalRecord.record.components
            : mainNormalizedRecord.components,
          path: alias,
          // 如果有原始记录，aliasOf为原始记录，如果没有原始记录就是它自己
          aliasOf: originalRecord
            ? originalRecord.record
            : mainNormalizedRecord,
        }) as typeof mainNormalizedRecord
      )
    }
  }

  let matcher: RouteRecordMatcher
  let originalMatcher: RouteRecordMatcher | undefined

  // 遍历normalizedRecords
  for (const normalizedRecord of normalizedRecords) {
    
    // 处理normalizedRecord.path为完整的path
    const { path } = normalizedRecord
    // 如果path不是以/开头，那么说明它不是根路由，需要拼接为完整的path
    // { path: '/a', children: [ { path: 'b' } ] } -> { path: '/a', children: [ { path: '/a/b' } ] }
    if (parent && path[0] !== '/') {
      const parentPath = parent.record.path
      const connectingSlash =
        parentPath[parentPath.length - 1] === '/' ? '' : '/'
      normalizedRecord.path =
        parent.record.path + (path && connectingSlash + path)
    }

    // 提示*应使用正则表示式形式
    if (__DEV__ && normalizedRecord.path === '*') {
      throw new Error(
        'Catch all routes ("*") must now be defined using a param with a custom regexp.\n' +
          'See more at https://next.router.vuejs.org/guide/migration/#removed-star-or-catch-all-routes.'
      )
    }

    // 创建一个路由记录匹配器
    matcher = createRouteRecordMatcher(normalizedRecord, parent, options)

    // 检查是否有丢失的参数
    if (__DEV__ && parent && path[0] === '/')
      checkMissingParamsInAbsolutePath(matcher, parent)

    // 如果有originalRecord，将matcher放入原始记录的alias中，以便后续能够删除
    if (originalRecord) {
      originalRecord.alias.push(matcher)
      // 检查originalRecord与matcher中动态参数是否相同
      if (__DEV__) {
        checkSameParams(originalRecord, matcher)
      }
    } else { // 没有originalRecord
      // 因为原始记录索引为0，所以originalMatcher为有原始记录所产生的matcher
      originalMatcher = originalMatcher || matcher
      // 如果matcher不是原始记录产生的matcher，说明此时matcher是由别名记录产生的，此时将matcher放入originalMatcher.alias中
      if (originalMatcher !== matcher) originalMatcher.alias.push(matcher)
      // 如果命名并且仅用于顶部记录，则删除路由（避免嵌套调用）
      if (isRootAdd && record.name && !isAliasRecord(matcher))
        removeRoute(record.name)
    }

    // 遍历children，递归addRoute
    if ('children' in mainNormalizedRecord) {
      const children = mainNormalizedRecord.children
      for (let i = 0; i < children.length; i++) {
        addRoute(
          children[i],
          matcher,
          originalRecord && originalRecord.children[i]
        )
      }
    }

    // 如果originalRecord是方法传入的，那么originalRecord继续保持
    // 如果originalRecord方法未传入。由于原始的matcher总是在索引为0的位置，所以如果有别名，那么这些别名的原始matcher会始终指向索引为0的位置
    originalRecord = originalRecord || matcher
    // 添加matcher
    insertMatcher(matcher)
  }

  // 返回一个删除原始matcher的方法
  return originalMatcher
    ? () => {
        removeRoute(originalMatcher!)
      }
    : noop
}

interface TokenStatic {
  type: TokenType.Static
  value: string
}

interface TokenParam {
  type: TokenType.Param
  regexp?: string
  value: string
  optional: boolean
  repeatable: boolean
}

interface TokenGroup {
  type: TokenType.Group
  value: Exclude<Token, TokenGroup>[]
}

export type Token = TokenStatic | TokenParam | TokenGroup

[
  [{ type: TokenType.Static, value: 'one' }],
  [{ type: TokenType.Static, value: 'two' }],
  [{ type: TokenType.Static, value: 'three' }]
]

[
  [
    {
      type: TokenType.Static,
      value: 'user',
    },
  ],
  [
    {
      type: TokenType.Param,
      value: 'id',
      regexp: '',
      repeatable: false,
      optional: false,
    }
  ]
]

[
  [
    {
      type: TokenType.Param,
      value: 'id',
      regexp: '\\d+',
      repeatable: false,
      optional: false,
    },
    {
      type: TokenType.Static,
      value: 'new'
    }
  ]
]

export const enum TokenType {
  Static,
  Param,
  Group,
}

const ROOT_TOKEN: Token = {
  type: TokenType.Static,
  value: '',
}

export function tokenizePath(path: string): Array<Token[]> {
  if (!path) return [[]]
  if (path === '/') return [[ROOT_TOKEN]]
  // 如果path不是以/开头，抛出错误
  if (!path.startsWith('/')) {
    throw new Error(
      __DEV__
        ? `Route paths should start with a "/": "${path}" should be "/${path}".`
        : `Invalid path "${path}"`
    )
  }
  
  function crash(message: string) {
    throw new Error(`ERR (${state})/"${buffer}": ${message}`)
  }

  // token所处状态
  let state: TokenizerState = TokenizerState.Static
  // 前一个状态
  let previousState: TokenizerState = state
  const tokens: Array<Token[]> = []
  //  声明一个片段，该片段最终会被存入tokens中
  let segment!: Token[]

  // 添加segment至tokens中，同时segment重新变为空数组
  function finalizeSegment() {
    if (segment) tokens.push(segment)
    segment = []
  }

  let i = 0
  let char: string
  let buffer: string = ''
  // custom regexp for a param
  let customRe: string = ''

  // 消费buffer，即生成token添加到segment中
  function consumeBuffer() {
    if (!buffer) return

    if (state === TokenizerState.Static) {
      segment.push({
        type: TokenType.Static,
        value: buffer,
      })
    } else if (
      state === TokenizerState.Param ||
      state === TokenizerState.ParamRegExp ||
      state === TokenizerState.ParamRegExpEnd
    ) {
      if (segment.length > 1 && (char === '*' || char === '+'))
        crash(
          `A repeatable param (${buffer}) must be alone in its segment. eg: '/:ids+.`
        )
      segment.push({
        type: TokenType.Param,
        value: buffer,
        regexp: customRe,
        repeatable: char === '*' || char === '+',
        optional: char === '*' || char === '?',
      })
    } else {
      crash('Invalid state to consume buffer')
    }
    // 消费完后置空
    buffer = ''
  }

  function addCharToBuffer() {
    buffer += char
  }

  // 遍历path
  while (i < path.length) {
    char = path[i++]

    // path='/\\:'
    if (char === '\\' && state !== TokenizerState.ParamRegExp) {
      previousState = state
      state = TokenizerState.EscapeNext
      continue
    }

    switch (state) {
      case TokenizerState.Static:
        if (char === '/') {
          if (buffer) {
            consumeBuffer()
          }
          // char === /时说明已经遍历完一层路由，这时需要将segment添加到tokens中
          finalizeSegment()
        } else if (char === ':') { // char为:时，因为此时状态是TokenizerState.Static，所以:后是参数，此时要把state变为TokenizerState.Param
          consumeBuffer()
          state = TokenizerState.Param
        } else { // 其他情况拼接buffer
          addCharToBuffer()
        }
        break

      case TokenizerState.EscapeNext:
        addCharToBuffer()
        state = previousState
        break

      case TokenizerState.Param:
        if (char === '(') { // 碰到(，因为此时state为TokenizerState.Param，说明后面是正则表达式，所以修改state为TokenizerState.ParamRegExp
          state = TokenizerState.ParamRegExp
        } else if (VALID_PARAM_RE.test(char)) {
          addCharToBuffer()
        } else { // 例如/:id/one，当遍历到第二个/时，消费buffer，state变为Static，并让i回退，回退后进入Static
          consumeBuffer()
          state = TokenizerState.Static
          if (char !== '*' && char !== '?' && char !== '+') i--
        }
        break

      case TokenizerState.ParamRegExp: 
        // it already works by escaping the closing )
        // TODO: is it worth handling nested regexp? like :p(?:prefix_([^/]+)_suffix)
        // https://paths.esm.dev/?p=AAMeJbiAwQEcDKbAoAAkP60PG2R6QAvgNaA6AFACM2ABuQBB#
        // is this really something people need since you can also write
        // /prefix_:p()_suffix
        if (char === ')') {
          // 如果是\\)的情况,customRe = customRe去掉\\ + char
          if (customRe[customRe.length - 1] == '\\')
            customRe = customRe.slice(0, -1) + char
          else state = TokenizerState.ParamRegExpEnd // 如果不是\\)说明正则表达式已经遍历完
        } else {
          customRe += char
        }
        break

      case TokenizerState.ParamRegExpEnd: // 正则表达式已经遍历完
        // 消费buffer
        consumeBuffer()
        // 重置state为Static
        state = TokenizerState.Static
        // 例如/:id(\\d+)new，当遍历到n时，使i回退，下一次进入Static分支中处理
        if (char !== '*' && char !== '?' && char !== '+') i--
        customRe = ''
        break

      default:
        crash('Unknown state')
        break
    }
  }

  // 如果遍历结束后，state还是ParamRegExp状态，说明正则是没有结束的，可能漏了)
  if (state === TokenizerState.ParamRegExp)
    crash(`Unfinished custom RegExp for param "${buffer}"`)

  // 遍历完path，进行最后一次消费buffer
  consumeBuffer()
  // 将segment放入tokens
  finalizeSegment()

  // 最后返回tokens
  return tokens
}

[
  [
    {
      type: TokenType.Param,
      value: 'id',
      regexp: '\\d+',
      repeatable: false,
      optional: false,
    },
    {
      type: TokenType.Static,
      value: 'new'
    }
  ]
]

const BASE_PATH_PARSER_OPTIONS: Required<_PathParserOptions> = {
  sensitive: false,
  strict: false,
  start: true,
  end: true,
}
const REGEX_CHARS_RE = /[.+*?^${}()[\]/\\]/g
export function tokensToParser(
  segments: Array<Token[]>,
  extraOptions?: _PathParserOptions
): PathParser {
  const options = assign({}, BASE_PATH_PARSER_OPTIONS, extraOptions)

  // the amount of scores is the same as the length of segments except for the root segment "/"
  const score: Array<number[]> = []
  // 正则的字符串形式
  let pattern = options.start ? '^' : ''
  // 保存路由中的动态参数
  const keys: PathParserParamKey[] = []

  for (const segment of segments) {
    // 用一个数组保存token的分数
    const segmentScores: number[] = segment.length ? [] : [PathScore.Root]

    // options.strict代表是否禁止尾部/，如果禁止了pattern追加/
    if (options.strict && !segment.length) pattern += '/'
    // 开始遍历每个token
    for (let tokenIndex = 0; tokenIndex < segment.length; tokenIndex++) {
      const token = segment[tokenIndex]
      // 当前子片段（单个token）的分数
      let subSegmentScore: number =
        PathScore.Segment +
        (options.sensitive ? PathScore.BonusCaseSensitive : 0)

      if (token.type === TokenType.Static) {
        // 在开始一个新的片段前pattern需要添加/
        if (!tokenIndex) pattern += '/'
        // 将token.value追加到pattern后，追加前token.value中的.、+、*、?、^、$等字符前面加上\\
        // 关于replace，参考MDN：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/String/replace
        pattern += token.value.replace(REGEX_CHARS_RE, '\\$&')
        subSegmentScore += PathScore.Static
      } else if (token.type === TokenType.Param) {
        const { value, repeatable, optional, regexp } = token
        keys.push({
          name: value,
          repeatable,
          optional,
        })
        const re = regexp ? regexp : BASE_PARAM_PATTERN
        // 用户自定义的正则需要验证正则的正确性
        if (re !== BASE_PARAM_PATTERN) {
          subSegmentScore += PathScore.BonusCustomRegExp
          // 使用前确保正则是正确的
          try {
            new RegExp(`(${re})`)
          } catch (err) {
            throw new Error(
              `Invalid custom RegExp for param "${value}" (${re}): ` +
                (err as Error).message
            )
          }
        }

        // /:chapters*
        // when we repeat we must take care of the repeating leading slash
        let subPattern = repeatable ? `((?:${re})(?:/(?:${re}))*)` : `(${re})`

        // prepend the slash if we are starting a new segment
        if (!tokenIndex)
          subPattern =
            // avoid an optional / if there are more segments e.g. /:p?-static
            // or /:p?-:p2
            optional && segment.length < 2
              ? `(?:/${subPattern})`
              : '/' + subPattern
        if (optional) subPattern += '?'

        pattern += subPattern

        subSegmentScore += PathScore.Dynamic
        if (optional) subSegmentScore += PathScore.BonusOptional
        if (repeatable) subSegmentScore += PathScore.BonusRepeatable
        if (re === '.*') subSegmentScore += PathScore.BonusWildcard
      }

      segmentScores.push(subSegmentScore)
    }

    score.push(segmentScores)
  }

  // only apply the strict bonus to the last score
  if (options.strict && options.end) {
    const i = score.length - 1
    score[i][score[i].length - 1] += PathScore.BonusStrict
  }

  // TODO: dev only warn double trailing slash
  if (!options.strict) pattern += '/?'

  if (options.end) pattern += '$'
  // allow paths like /dynamic to only match dynamic or dynamic/... but not dynamic_something_else
  else if (options.strict) pattern += '(?:/|$)'

  // 根据组装好的pattern创建正则表达式，options.sensitive决定是否区分大小写
  const re = new RegExp(pattern, options.sensitive ? '' : 'i')

  // 根据path获取动态参数对象
  function parse(path: string): PathParams | null {
    const match = path.match(re)
    const params: PathParams = {}

    if (!match) return null

    for (let i = 1; i < match.length; i++) {
      const value: string = match[i] || ''
      const key = keys[i - 1]
      params[key.name] = value && key.repeatable ? value.split('/') : value
    }

    return params
  }

  // 根据传入的动态参数对象，转为对应的path
  function stringify(params: PathParams): string {
    let path = ''
    // for optional parameters to allow to be empty
    let avoidDuplicatedSlash: boolean = false
    for (const segment of segments) {
      if (!avoidDuplicatedSlash || !path.endsWith('/')) path += '/'
      avoidDuplicatedSlash = false

      for (const token of segment) {
        if (token.type === TokenType.Static) {
          path += token.value
        } else if (token.type === TokenType.Param) {
          const { value, repeatable, optional } = token
          const param: string | string[] = value in params ? params[value] : ''

          if (Array.isArray(param) && !repeatable)
            throw new Error(
              `Provided param "${value}" is an array but it is not repeatable (* or + modifiers)`
            )
          const text: string = Array.isArray(param) ? param.join('/') : param
          if (!text) {
            if (optional) {
              // if we have more than one optional param like /:a?-static and there are more segments, we don't need to
              // care about the optional param
              if (segment.length < 2 && segments.length > 1) {
                // remove the last slash as we could be at the end
                if (path.endsWith('/')) path = path.slice(0, -1)
                // do not append a slash on the next iteration
                else avoidDuplicatedSlash = true
              }
            } else throw new Error(`Missing required param "${value}"`)
          }
          path += text
        }
      }
    }

    return path
  }

  return {
    re,
    score,
    keys,
    parse,
    stringify,
  }
}

export function createRouteRecordMatcher(
  record: Readonly<RouteRecord>,
  parent: RouteRecordMatcher | undefined,
  options?: PathParserOptions
): RouteRecordMatcher {
  // 生成parser对象
  const parser = tokensToParser(tokenizePath(record.path), options)

  // 如果有重复的动态参数命名进行提示
  if (__DEV__) {
    const existingKeys = new Set<string>()
    for (const key of parser.keys) {
      if (existingKeys.has(key.name))
        warn(
          `Found duplicated params with name "${key.name}" for path "${record.path}". Only the last one will be available on "$route.params".`
        )
      existingKeys.add(key.name)
    }
  }

  // 
  const matcher: RouteRecordMatcher = assign(parser, {
    record,
    parent,
    // these needs to be populated by the parent
    children: [],
    alias: [],
  })

  if (parent) {
    // 两者都是alias或两者都不是alias
    if (!matcher.record.aliasOf === !parent.record.aliasOf)
      parent.children.push(matcher)
  }

  return matcher
}

function resolve(
    location: Readonly<MatcherLocationRaw>,
    currentLocation: Readonly<MatcherLocation>
  ): MatcherLocation {
    let matcher: RouteRecordMatcher | undefined
    let params: PathParams = {}
    let path: MatcherLocation['path']
    let name: MatcherLocation['name']

    if ('name' in location && location.name) { // 如果location存在name属性，可根据name从matcherMap获取matcher
      matcher = matcherMap.get(location.name)

      if (!matcher)
        throw createRouterError<MatcherError>(ErrorTypes.MATCHER_NOT_FOUND, {
          location,
        })

      name = matcher.record.name
      // 合并location.params和currentLocation中的params
      params = assign(
        paramsFromLocation(
          currentLocation.params,
          matcher.keys.filter(k => !k.optional).map(k => k.name)
        ),
        location.params
      )
      // 如果不能通过params转为path抛出错误
      path = matcher.stringify(params)
    } else if ('path' in location) { // 如果location存在path属性，根据path从matchers获取对应matcher
      path = location.path

      if (__DEV__ && !path.startsWith('/')) {
        warn(
          `The Matcher cannot resolve relative paths but received "${path}". Unless you directly called \`matcher.resolve("${path}")\`, this is probably a bug in vue-router. Please open an issue at https://new-issue.vuejs.org/?repo=vuejs/router.`
        )
      }

      matcher = matchers.find(m => m.re.test(path))

      if (matcher) {
        // 通过parse函数获取params
        params = matcher.parse(path)!
        name = matcher.record.name
      }
    } else { // 如果location中没有name、path属性，就使用currentLocation的name或path获取matcher
      matcher = currentLocation.name
        ? matcherMap.get(currentLocation.name)
        : matchers.find(m => m.re.test(currentLocation.path))
      if (!matcher)
        throw createRouterError<MatcherError>(ErrorTypes.MATCHER_NOT_FOUND, {
          location,
          currentLocation,
        })
      name = matcher.record.name
      params = assign({}, currentLocation.params, location.params)
      path = matcher.stringify(params)
    }

    // 使用一个数组存储匹配到的所有路由
    const matched: MatcherLocation['matched'] = []
    let parentMatcher: RouteRecordMatcher | undefined = matcher
    while (parentMatcher) {
      // 父路由始终在数组的开头
      matched.unshift(parentMatcher.record)
      parentMatcher = parentMatcher.parent
    }

    return {
      name,
      path,
      params,
      matched,
      meta: mergeMetaFields(matched),
    }
  }

function removeRoute(matcherRef: RouteRecordName | RouteRecordMatcher) {
  // 如果是路由名字：string或symbol
  if (isRouteName(matcherRef)) {
    const matcher = matcherMap.get(matcherRef)
    if (matcher) {
      // 删除matcher
      matcherMap.delete(matcherRef)
      matchers.splice(matchers.indexOf(matcher), 1)
      // 清空matcher中的children与alias，
      matcher.children.forEach(removeRoute)
      matcher.alias.forEach(removeRoute)
    }
  } else {
    const index = matchers.indexOf(matcherRef)
    if (index > -1) {
      matchers.splice(index, 1)
      if (matcherRef.record.name) matcherMap.delete(matcherRef.record.name)
      matcherRef.children.forEach(removeRoute)
      matcherRef.alias.forEach(removeRoute)
    }
  }
}

function getRoutes() {
  return matchers
}

function getRecordMatcher(name: RouteRecordName) {
  return matcherMap.get(name)
}

function insertMatcher(matcher: RouteRecordMatcher) {
  let i = 0
  while (
    i < matchers.length &&
    comparePathParserScore(matcher, matchers[i]) >= 0 &&
    (matcher.record.path !== matchers[i].record.path ||
      !isRecordChildOf(matcher, matchers[i]))
  )
    i++
  matchers.splice(i, 0, matcher)
  // only add the original record to the name map
  if (matcher.record.name && !isAliasRecord(matcher))
    matcherMap.set(matcher.record.name, matcher)
}

// 返回0表示a与b相等；返回>0，b先排序；返回<0，a先排序
function compareScoreArray(a: number[], b: number[]): number {
  let i = 0
  while (i < a.length && i < b.length) {
    const diff = b[i] - a[i]
    // 一旦a与b对位索引对应的值有差值，直接返回
    if (diff) return diff

    i++
  }

  if (a.length < b.length) {
    // 如果a.length为1且第一个值的分数为PathScore.Static + PathScore.Segment，返回-1，表示a先排序，否则返回1，表示b先排序
    return a.length === 1 && a[0] === PathScore.Static + PathScore.Segment
      ? -1
      : 1
  } else if (a.length > b.length) {
    // 如果b.length为1且第一个值的分数为PathScore.Static + PathScore.Segment，返回-1，表示b先排序，否则返回1，表示a先排序
    return b.length === 1 && b[0] === PathScore.Static + PathScore.Segment
      ? 1
      : -1
  }

  return 0
}

// 返回0表示a与b相等；返回>0，b先排序；返回<0，a先排序
export function comparePathParserScore(a: PathParser, b: PathParser): number {
  let i = 0
  const aScore = a.score
  const bScore = b.score
  while (i < aScore.length && i < bScore.length) {
    const comp = compareScoreArray(aScore[i], bScore[i])
    if (comp) return comp

    i++
  }

  return bScore.length - aScore.length
}

if (a.length > b.length) {
  return b.length === 1 && b[0] === PathScore.Static + PathScore.Segment
    ? 1
    : -1
}

if (a.length < b.length) {
  return a.length === 1 && a[0] === PathScore.Static + PathScore.Segment
    ? -1
    : 1
}

export interface PathParser {
  re: RegExp
  score: Array<number[]>
  keys: PathParserParamKey[]
  parse(path: string): PathParams | null
  stringify(params: PathParams): string
}
export interface RouteRecordMatcher extends PathParser {
  record: RouteRecord
  parent: RouteRecordMatcher | undefined
  children: RouteRecordMatcher[]
  // aliases that must be removed when removing this record
  alias: RouteRecordMatcher[]
}