首页 > 其他分享 >最佳实践:路径路由匹配规则的设计与实现

最佳实践:路径路由匹配规则的设计与实现

时间:2023-05-10 17:25:19浏览次数:45  
标签:routeSplit return 路径 路由 匹配 pi pathSplit

最佳实践:路径路由匹配规则的设计与实现

作者:哲思
时间: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 的格式)

URI格式

该格式的大致含义是某人(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这一部分,如下图蓝色区域,

url与路径

蓝色区域已经完整描述了资源的位置,protocol 是补充描述了访问资源的方式,username:password 是附带的认证信息,search 和 hash 则描述的对某一个资源的进一步处理。而hostname:port/path就是一个路径,每个路径分段描述的是某个层级的位置节点。

比如,URN 中,路径的每个路径分段则描述不同命名空间及命名空间下的名字。

路径路由匹配规则的设计

了解了什么是路径,接下来给出路径路由匹配规则的定义描述:

  • R 模式:正则模式,格式:R:正则表达式

    该模式下,完全采用正则表达式格式进行匹配。

  • 标准模式:标准路径路由描述表达式,格式形如:/**/xxx/*/xxx,由多个路径分段的分段列表组成,要求路径分段列表全匹配

    具体语法:

    • 分隔方法

      默认使用 '/' 分隔符分隔多个路径分段

      • 支持自定义路由分隔方法路径分隔方法
    • 路径分段

      • 每个具体的路径分段默认采用完全字符串匹配
      • r 模式:路径分段正则模式,该路径分段采用正则表达式进行匹配,格式:r:正则表达式
    • 通配符 '?'

      匹配任意一段或 0 段路径分段,在满足后续部分匹配的情况下优先不匹配

    • 通配符 '*'

      匹配任意一端路径,不可匹配空或不匹配

    • 通配符 '**'

      匹配任意多段路径分段,不保证尽可能满足的最短匹配原则,即在满足紧接的后续非通配符部分匹配的情况下尽可能少的匹配

    • 通配符 '***'

      匹配任意多段路径分段,保证尽可能满足的最长匹配原则,即在满足后续匹配的情况下尽可能多的匹配

举一些例子:

路由 匹配路径 不匹配路径
a/?/c a/b/c、a//c、a/c a/c/d
a/*/c a/b/c a/c
a/b/* a/b/c a/b
**/b/c a/b/c、b/c、a/a/b/b/c b/c/b/c
a/***/c/* a/c/c、a/c/b/c/d a/b/c
a/**/c/* a/c/c a/c/b/c/d

一组路径 "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
}

后记

本次分享了在项目中的一个细节设计,后续会继续分享在工作、学习和生活中的点点滴滴,也欢迎大家在评论区共同讨论或与我邮件沟通。

标签:routeSplit,return,路径,路由,匹配,pi,pathSplit
From: https://www.cnblogs.com/zhe-si/p/17388551.html

相关文章

  • Vue的Router 在首页获取 fullPath 一直都是根路由‘/‘ ?
    在main.j中获取的this.$route.fullpath一直都是'/',因为给路由fullPath赋值是微任务,我们直接获取肯定只能拿到根路由“/”;解决方案:1.给路由fullPath赋值是微任务,那么只需要通过宏任务获取fullPath就可以了,setTimeout(()=>{console.log(this.$route.fullPath)},2000) 2......
  • Umi配置路由
    一、Umi路由的概念在Umi中,你可以在 .umirc.ts 文件中使用 routes 属性来配置路由。routes 属性是一个数组,每个元素都表示一个路由对象。每个路由对象都包含以下属性:path:表示路由路径,可以是字符串或正则表达式。component:表示路由组件的路径,可以是字符串或函数。r......
  • 1、华为路由器百兆或千兆口解决IP配置问题
    遇到的问题:通常情况下,华为路由器千兆口可以配置IP,无需划分VLAN都可以。但是,百兆口如果是不支持三层交换的话,就无法直接进行IP配置。此时,需要配置VLAN,将VLAN加入端口,并且pvid还得加上。 注意:交换机和路由器都类似。最后就是不同网段,应使用相关协议、配置路由等。......
  • 修改下载地址路径
    fromselenium.webdriver.chrome.optionsimportOptionschrome_options=Options()    prefs={"download.default_directory":'{}'.format('下载地址')} #下载路径为D:\电子保单下载    chrome_options.add_experimental_option(&quo......
  • c#判断指定路径的目录/文件是否存在
    Directory.Exists(stringpath)是C#中用来判断指定目录是否存在的方法。它的返回值是bool类型,true表示目录存在,否则表示目录不存在。使用该方法的完整攻略如下:1.确定需要判断的目录路径,可以是绝对路径或者相对路径。2.使用Directory.Exists(stringpath)方法对目录进行判断。3......
  • Java获取当前路径(Linux+Windows)
    Java获取当前路径(Linux+Windows)获取当前路径(兼容Linux、Windows):StringcurPath=System.getProperty("user.dir");log.info("===========当前路径===========curPath:{}",curPath);输出结果:===========当前路径===========curPath:/home/lizhm......
  • KingbaseES V8R6备份恢复系列之 -- system-Id不匹配备份故障
    ​KingbaseESV8R6备份恢复案例之---system-Id不匹配备份故障案例说明:在KingbaseESV8R6执行备份时,在sys_log日志中出现system-id不一致的故障并伴随有归档失败,故障如下图所示:适用版本:KingbaseESV8R6一、问题分析1、查看当前数据库system-id可以通过sys_controldata-D......
  • KingbaseES 语句like前匹配如何使用索引
    前言有现场同事反馈sql语句like使用后缀通配符%不走索引。至于执行计划没走索引的原因与KingbaseES数据库中的排序规则相关。测试测试环境:KingbaseESV8R6C7test=#\dtestTable"public.test"Column|Type|Collation|Nullable|Default--......
  • 「TJOI2018」智力竞赛(二分+DAG最小可相交路径覆盖)
    https://loj.ac/problem/2574这个题目描述扎心了。简要题意:用n+1条可以相交的路径去覆盖DAG,使得没被覆盖的点的权值的最小值最大。首先二分答案,问题转换为有一些点一定要被覆盖,问n+1条路径内有没有解。这个可以暴力费用流,每个点拆成两个点,\(i->i',r=1\),如果这个点必选,则费用为inf,......
  • Codeforces [Hello 2020] 1284F New Year and Social Network(图论匹配推理+lct)
    https://codeforces.com/contest/1284/problem/F题目大意:有两个大小为n的树T1和T2.T2中的每条边(u,v)可以匹配T1中u到v路径上的所有边。求最大匹配,并给出方案。\(1<=n<=250000\)题解:首先你需要观察样例大胆猜想一定有完美匹配。考虑T1中的一个叶子x和它的父亲y。显然的是,从T2中随......