policy: fix as-path match optimization

following as-path pattern will be optimized

- ^<asn>_ # left-most
- _<asn>$ # origin
- _<asn>_ # include
- ^<asn>$ # only

Signed-off-by: ISHIDA Wataru <ishida.wataru@lab.ntt.co.jp>

3 files changed, 75 insertions, 52 deletions

diff --git a/docs/sources/policy.md b/docs/sources/policy.md
index 5b99c52e..5d4a0c05 100644
--- a/docs/sources/policy.md
+++ b/docs/sources/policy.md
@@ -427,15 +427,17 @@ part. Like PrefixSets and NeighborSets, each can have multiple sets and each set
  |------------------|-------------------|------------|----------|
  | AsPathSet        | as path value     | "^65100"   |          |
 
- The AS path regular expression is compatible with [Quagga](http://www.nongnu.org/quagga/docs/docs-multi/AS-Path-Regular-Expression.html) and Cisco. Some examples follow:
-
-    - From: "^65100" means the route is passed from AS 65100 directly.
-    - Any: "65100" means the route comes through AS 65100.
-    - Origin: "65100$" means the route is originated by AS 65100.
-    - Only: "^65100$" means the route is originated by AS 65100 and comes from it directly.
-    - ^65100_65001
-    - 65100_[0-9]+_.*$
-    - ^6[0-9]_5.*_65.?00$
+ The AS path regular expression is compatible with [Quagga](http://www.nongnu.org/quagga/docs/docs-multi/AS-Path-Regular-Expression.html) and Cisco.
+ Note Character `_` has special meaning. It is abbreviation for `(^|[,{}() ]|$)`.
+
+ Some examples follow:
+    - From: `^65100_` means the route is passed from AS 65100 directly.
+    - Any: `_65100_` means the route comes through AS 65100.
+    - Origin: `_65100$` means the route is originated by AS 65100.
+    - Only: `^65100$` means the route is originated by AS 65100 and comes from it directly.
+    - `^65100_65001`
+    - `65100_[0-9]+_.*$`
+    - `^6[0-9]_5.*_65.?00$`
 
   ##### Examples
   - example 1
@@ -445,7 +447,7 @@ part. Like PrefixSets and NeighborSets, each can have multiple sets and each set
   # example 1
   [[defined-sets.bgp-defined-sets.as-path-sets]]
     as-path-set-name = "aspath1"
-    as-path-list = ["^65100"]
+    as-path-list = ["^65100_"]
   ```
 
   - example 2
diff --git a/table/policy.go b/table/policy.go
index 513e93fe..0692a066 100644
--- a/table/policy.go
+++ b/table/policy.go
@@ -540,6 +540,7 @@ const (
 	INCLUDE singleAsPathMatchMode = iota
 	LEFT_MOST
 	ORIGIN
+	ONLY
 )
 
 type singleAsPathMatch struct {
@@ -554,11 +555,13 @@ func (lhs *singleAsPathMatch) Equal(rhs *singleAsPathMatch) bool {
 func (lhs *singleAsPathMatch) String() string {
 	switch lhs.mode {
 	case INCLUDE:
-		return fmt.Sprintf("%d", lhs.asn)
+		return fmt.Sprintf("_%d_", lhs.asn)
 	case LEFT_MOST:
-		return fmt.Sprintf("^%d", lhs.asn)
+		return fmt.Sprintf("^%d_", lhs.asn)
 	case ORIGIN:
-		return fmt.Sprintf("%d$", lhs.asn)
+		return fmt.Sprintf("_%d$", lhs.asn)
+	case ONLY:
+		return fmt.Sprintf("^%d$", lhs.asn)
 	}
 	return ""
 }
@@ -582,34 +585,43 @@ func (m *singleAsPathMatch) Match(aspath []uint32) bool {
 		if m.asn == aspath[len(aspath)-1] {
 			return true
 		}
+	case ONLY:
+		if len(aspath) == 1 && m.asn == aspath[0] {
+			return true
+		}
 	}
 	return false
 }
 
 func NewSingleAsPathMatch(arg string) *singleAsPathMatch {
+	leftMostRe := regexp.MustCompile("$\\^([0-9]+)_^")
+	originRe := regexp.MustCompile("^_([0-9]+)\\$$")
+	includeRe := regexp.MustCompile("^_([0-9]+)_$")
+	onlyRe := regexp.MustCompile("^\\^([0-9]+)\\$$")
 	switch {
-	case len(arg) == 0:
-		return nil
-	case arg[0] == '^':
-		if asn, err := strconv.Atoi(arg[1:]); err == nil {
-			return &singleAsPathMatch{
-				asn:  uint32(asn),
-				mode: LEFT_MOST,
-			}
-		}
-	case arg[len(arg)-1] == '$':
-		if asn, err := strconv.Atoi(arg[:len(arg)-1]); err == nil {
-			return &singleAsPathMatch{
-				asn:  uint32(asn),
-				mode: ORIGIN,
-			}
-		}
-	default:
-		if asn, err := strconv.Atoi(arg); err == nil {
-			return &singleAsPathMatch{
-				asn:  uint32(asn),
-				mode: INCLUDE,
-			}
+	case leftMostRe.MatchString(arg):
+		asn, _ := strconv.Atoi(leftMostRe.FindStringSubmatch(arg)[1])
+		return &singleAsPathMatch{
+			asn:  uint32(asn),
+			mode: LEFT_MOST,
+		}
+	case originRe.MatchString(arg):
+		asn, _ := strconv.Atoi(originRe.FindStringSubmatch(arg)[1])
+		return &singleAsPathMatch{
+			asn:  uint32(asn),
+			mode: ORIGIN,
+		}
+	case includeRe.MatchString(arg):
+		asn, _ := strconv.Atoi(includeRe.FindStringSubmatch(arg)[1])
+		return &singleAsPathMatch{
+			asn:  uint32(asn),
+			mode: INCLUDE,
+		}
+	case onlyRe.MatchString(arg):
+		asn, _ := strconv.Atoi(onlyRe.FindStringSubmatch(arg)[1])
+		return &singleAsPathMatch{
+			asn:  uint32(asn),
+			mode: ONLY,
 		}
 	}
 	return nil
@@ -1253,33 +1265,40 @@ func (c *AsPathCondition) ToApiStruct() *api.MatchSet {
 }
 
 func (c *AsPathCondition) Evaluate(path *Path, _ *PolicyOptions) bool {
-	result := false
-	aspath := path.GetAsSeqList()
-	for _, m := range c.set.singleList {
-		result = m.Match(aspath)
-		if c.option == MATCH_OPTION_ALL && !result {
-			break
-		}
-		if c.option == MATCH_OPTION_ANY && result {
-			break
+	if len(c.set.singleList) > 0 {
+		aspath := path.GetAsSeqList()
+		for _, m := range c.set.singleList {
+			result := m.Match(aspath)
+			if c.option == MATCH_OPTION_ALL && !result {
+				return false
+			}
+			if c.option == MATCH_OPTION_ANY && result {
+				return true
+			}
+			if c.option == MATCH_OPTION_INVERT && result {
+				return false
+			}
 		}
 	}
-	if (c.option == MATCH_OPTION_ALL && result) || (c.option == MATCH_OPTION_ANY && !result) {
+	if len(c.set.list) > 0 {
 		aspath := path.GetAsString()
 		for _, r := range c.set.list {
-			result = r.MatchString(aspath)
+			result := r.MatchString(aspath)
 			if c.option == MATCH_OPTION_ALL && !result {
-				break
+				return false
 			}
 			if c.option == MATCH_OPTION_ANY && result {
-				break
+				return true
+			}
+			if c.option == MATCH_OPTION_INVERT && result {
+				return false
 			}
 		}
 	}
-	if c.option == MATCH_OPTION_INVERT {
-		result = !result
+	if c.option == MATCH_OPTION_ANY {
+		return false
 	}
-	return result
+	return true
 }
 
 func NewAsPathConditionFromApiStruct(a *api.MatchSet, m map[string]DefinedSet) (*AsPathCondition, error) {
diff --git a/table/policy_test.go b/table/policy_test.go
index ab4b4067..be301593 100644
--- a/table/policy_test.go
+++ b/table/policy_test.go
@@ -911,7 +911,7 @@ func TestAsPathCondition(t *testing.T) {
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{1000, 7521, 100}, false),
 	}
 
-	tests["^65001.*65535$"] = []astest{
+	tests["^65001( |_.*_)65535$"] = []astest{
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65001, 65535}, true),
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65001, 65001, 65535}, true),
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65001, 65002, 65003, 65535}, true),
@@ -919,6 +919,8 @@ func TestAsPathCondition(t *testing.T) {
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65002, 65535}, false),
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65002, 65001, 65535}, false),
 		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65001, 65535, 65002}, false),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{650019, 65535}, false),
+		makeTest(bgp.BGP_ASPATH_ATTR_TYPE_SEQ, []uint32{65001, 165535}, false),
 	}
 
 	for k, v := range tests {