最佳實踐：路徑路由匹配規則的設計與實作

作者：哲思
時間：2023.5.9
郵箱：[email protected]
GitHub：zhe-si (哲思) (github.com)

前言

時間一晃研究生都過去大半年了，學了些東西，也做了些專案，借著博客總結一下，這次先聊一個簡單的話題開個頭，

開發中，常用形似 “a/b/c” 的描述方式來描述路徑、定位資源，有著層次化和可讀性高的特點，最經典的例子就是 URL（統一資源定位符），第二節會進行簡要介紹，

將資源都路徑化后，可以通過每一段路徑精確的匹配來唯一的確定一個資源，但有時候，需要對具有相關特征的一組資源進行統一的描述或操作，比如，將所有獲得用戶資訊的請求都路由到一個指定的處理程式上，請求的 URL 中包含不同用戶 id 路徑分段指向不同用戶資訊資源，再比如，界面中導航欄包含圖片組（包含圖1、2、3）和文本組（包含文本1、2、3），在訪問圖片組下不同圖片時打開圖片展示器而在訪問文本組的文本時打開文本展示器，

基于上述場景的需求，需要一種簡單而通用的路徑路由匹配規則，最強大的方式是直接使用正則運算式來描述一組路徑，但在描述一些復雜的路徑場景時，正則運算式使用起來非常繁瑣和困難，比如，匹配這樣一組路徑 "x1/a/x2/a"，x1 表示任意長的最短匹配路徑，x2表示任意長的最長匹配路徑，大家可以嘗試用正則運算式實作，并和本文設計的匹配規則的描述進行對比，

本文設計并實作了一種專用于路徑路由匹配的規則，以一種簡單而通用的方式描述一組路徑的特征，來簡化這種場景路由描述難度，讓小白可以快速學習并上手，

什么是URL？什么是路徑？

首先，需要明確一下什么是資源？什么是路徑？

上面提到的 URL（統一資源定位符）是 URI（統一資源識別符號）的一種分類，

URI 的本質語意是標識一個資源，資源可以是一張圖片、一個檔案、一個服務、一個用戶等具體或抽象的物體，官方（RFC2396）將其格式標準化為如下格式（就是 URL 的格式）

該格式的大致含義是某人（user:pass）用某種方式（protocol）訪問某個主機埠（hostname:port）某個路徑（pathName）的資源，同時可用 search 對該資源做篩選、排序等操作、用 hash 訪問資源的片段（子資源），

而標識一個資源，可以通過描述位置或名字的方式，所以 URI 包括 URL 和 URN（統一資源名稱），

• 描述位置：用資源所處的地址來描述該資源，該描述指定了在特定地址的資源而不特指某一個具體的資源，也就是說實際指向的資源可能會隨時間發生變化，資源的位置描述也會隨資源本身位置的變化而變化，如 URL，
• 描述名字：用一個全域唯一的識別符號持久的標記一個特定的資源，不會隨著時間或位置變化而改變指向的資源，如 URN（例：urn:oasis:names:specification:docbook:dtd:xml:4.1.2），常用于 Map、Redis 中 KEY 的定義等場景，

但不管是位置描述還是名字描述、不管具體的格式是什么，都可以把它們抽象為一種“路徑”，只是路徑的描述的含義不同、分隔符不同，

比如，URL 中，最核心的部分就是hostname:port/path這一部分，如下圖藍色區域，

藍色區域已經完整描述了資源的位置，protocol 是補充描述了訪問資源的方式，username:password 是附帶的認證資訊，search 和 hash 則描述的對某一個資源的進一步處理，而hostname:port/path就是一個路徑，每個路徑分段描述的是某個層級的位置節點，

比如，URN 中，路徑的每個路徑分段則描述不同命名空間及命名空間下的名字，

路徑路由匹配規則的設計

了解了什么是路徑，接下來給出路徑路由匹配規則的定義描述：

• R 模式：正則模式，格式：R:正則運算式

  該模式下，完全采用正則運算式格式進行匹配，

• 標準模式：標準路徑路由描述運算式，格式形如：/**/xxx/*/xxx，由多個路徑分段的分段串列組成，要求路徑分段串列全匹配

  具體語法：

  • 分隔方法

    默認使用 '/' 分隔符分隔多個路徑分段

    • 支持自定義路由分隔方法和路徑分隔方法

  • 路徑分段

    • 每個具體的路徑分段默認采用完全字串匹配
    • r 模式：路徑分段正則模式，該路徑分段采用正則運算式進行匹配，格式：r:正則運算式

  • 通配符 '?'

    匹配任意一段或 0 段路徑分段，在滿足后續部分匹配的情況下優先不匹配

  • 通配符 '*'

    匹配任意一端路徑，不可匹配慷訓不匹配

  • 通配符 '**'

    匹配任意多段路徑分段，不保證盡可能滿足的最短匹配原則，即在滿足緊接的后續非通配符部分匹配的情況下盡可能少的匹配

  • 通配符 '***'

    匹配任意多段路徑分段，保證盡可能滿足的最長匹配原則，即在滿足后續匹配的情況下盡可能多的匹配

舉一些例子：

一組路徑 "x1/a/x2/a"，x1 表示任意長的最短匹配路徑，x2表示任意長的最長匹配路徑，使用標準路徑路由描述運算式描述就是**/a/***/b，

其中，最常用的通配符是 "**"，通過不保證盡可能匹配的方式最短匹配，確保匹配的是我們直觀預期的路徑，比如如下目錄結構，

- common
	- A.java
	- B.java
	- a.conf
	- impl
		- common
			- Utils.java
		- AImpl.java
		- BImpl.java

我們希望匹配介面 A 和 B 的 java 檔案，而不匹配到 impl 里的實作類，可以采用如下匹配方式：**/common/r:.*\.java，

路徑路由匹配規則的實作

本文采用 kotlin 進行實作，重點位置已經進行注釋說明，源代碼可見倉庫，

/**
 * **路由匹配**
 * - 若 "R:" 開頭，則為正則模式，采用正則運算式直接匹配
 * - 其他情況，采用標準路由模式[matchStdRoutePattern]進行匹配
 *
 * @author lq
 * @version 1.0
 */
fun matchRoutePattern(routePattern: String, path: String): Boolean {
    return if (routePattern.startsWith("R:")) {
        Regex(routePattern.substring(2)).matches(path)
    } else {
        matchStdRoutePattern(routePattern, path)
    }
}

/**
 * **路由模式**：路由的特定描述運算式，形如 / ** /xxx/ * /xxx/
 *
 * 語法：
 * - 以 '/'([PATH_DELIMITER]) 分隔的路徑運算式，要求全匹配路徑，首尾的分隔符可以省略
 * - 每一段路徑描述默認采用字串完全匹配方式，也可通過 "r:" 開頭標記該段采用正則運算式匹配
 * - 使用通配符 "?" 可以匹配任意一段或 0 段路徑，優先不匹配
 * - 使用通配符 "*" 可以匹配任意一段路徑
 * - 使用通配符 "**" 可以匹配任意多段路徑，最短匹配原則
 * - 使用通配符 "***" 可以匹配任意多段路徑，最長匹配原則
 */
fun matchStdRoutePattern(routePattern: String, path: String): Boolean {
    val routeSplit = splitRoute(routePattern)
    val pathSplit = splitPath(path)
    return matchRoutePatternSplit(routeSplit, 0, pathSplit, 0)
}

/**
 * 路由分隔方法
 */
val splitRoute: (String) -> List<String> = ::splitPathSimple
/**
 * 路徑分隔方法
 */
val splitPath: (String) -> List<String> = ::splitPathSimple

/**
 * 簡單決議路徑為路徑分段串列
 */
private fun splitPathSimple(routePattern: String): List<String> {
    val pathDelimiter = '/'
    return routePattern.trim(pathDelimiter).split(pathDelimiter).filter { p -> p.isNotEmpty() }
}

private fun matchRoutePatternSplit(routeSplit: List<String>, ri: Int, pathSplit: List<String>, pi: Int): Boolean {
    if (ri >= routeSplit.size) {
        return pi >= pathSplit.size
    }
    if (pi >= pathSplit.size) {
        for (i in ri until routeSplit.size) {
            if (routeSplit[i] !in listOf("?", "**", "***")) return false
        }
        return true
    }
    when (routeSplit[ri].trim()) {
        "?" -> {
            if (matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi)) return true
            return matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi + 1)
        }
        "*" -> {
            return matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi + 1)
        }
        "**" -> {
            for (i in 0 until pathSplit.size - pi) {
                val isShortMatch = matchRoutePatternShort(routeSplit, ri + 1, pathSplit, pi + i, false)
                if (isShortMatch.first) return true
                if (isShortMatch.second) return false
            }
            return matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi + pathSplit.size - pi)
        }
        "***" -> {
            for (i in pathSplit.size - pi downTo 1) {
                if (matchRoutePatternSplit(routeSplit, pi + 1, pathSplit, pi + i)) return true
            }
            return matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi)
        }
        else -> {
            if (!checkRouteSegPattern(routeSplit[ri], pathSplit[pi])) return false
            return matchRoutePatternSplit(routeSplit, ri + 1, pathSplit, pi + 1)
        }
    }
}

/**
 * 最短原則匹配，回傳 (是否匹配, 是否已經最短匹配)
 */
private fun matchRoutePatternShort(routeSplit: List<String>, ri: Int, pathSplit: List<String>, pi: Int, isShortMatch: Boolean): Pair<Boolean, Boolean> {
    if (ri >= routeSplit.size) {
        return (pi >= pathSplit.size) to isShortMatch
    }
    if (pi >= pathSplit.size) {
        for (i in ri until routeSplit.size) {
            if (routeSplit[i] !in listOf("?", "**", "***")) return false to isShortMatch
        }
        return true to isShortMatch
    }
    when (routeSplit[ri].trim()) {
        "?" -> {
            val isMatch = matchRoutePatternShort(routeSplit, ri + 1, pathSplit, pi, isShortMatch)
            if (isMatch.first) return isMatch
            return matchRoutePatternShort(routeSplit, ri + 1, pathSplit, pi + 1, isShortMatch)
        }
        "*" -> {
            return matchRoutePatternShort(routeSplit, ri + 1, pathSplit, pi + 1, isShortMatch)
        }
        "**" -> {
            return matchRoutePatternSplit(routeSplit, ri, pathSplit, pi) to isShortMatch
        }
        "***" -> {
            return matchRoutePatternSplit(routeSplit, ri, pathSplit, pi) to isShortMatch
        }
        else -> {
            return if (checkRouteSegPattern(routeSplit[ri], pathSplit[pi])) {
                matchRoutePatternShort(routeSplit, ri + 1, pathSplit, pi + 1, true)
            } else {
                false to isShortMatch
            }
        }
    }
}

/**
 * 路徑分段匹配檢查
 */
private fun checkRouteSegPattern(routeSeg: String, pathSeg: String): Boolean {
    if (routeSeg.startsWith("r:")) {
        if (Regex(routeSeg.substring(2)).matches(pathSeg)) {
            return true
        }
    } else if (routeSeg == pathSeg) return true
    return false
}

后記

本次分享了在專案中的一個細節設計，后續會繼續分享在作業、學習和生活中的點點滴滴，也歡迎大家在評論區共同討論或與我郵件溝通，

本文來自博客園，作者：_哲思，轉載請注明原文鏈接：https://www.cnblogs.com/zhe-si/p/17388551.html

標籤：其他

上一篇：文盤Rust —— rust連接oss | 京東云技術團隊

下一篇：返回列表