Use local reverse

Signed-off-by: Jeroen Simonetti <jeroen@simonetti.nl>
jsimonetti · Nov 1, 2023 · 3337785 · 3337785
1 parent 76a930a
commit 3337785
Show file tree

Hide file tree

Showing 4 changed files with 47 additions and 14 deletions.
diff --git a/.github/workflows/nix-build.yaml b/.github/workflows/nix-build.yaml
@@ -19,6 +19,9 @@ jobs:
 
     steps:
       - uses: actions/checkout@v4
+        with:
+          repository: ${{ github.event.pull_request.head.repo.full_name }}
+          ref: ${{ github.event.pull_request.head.ref }}
 
       - name: Get changed files
         id: changed-files
@@ -58,7 +61,7 @@ jobs:
           git config --global user.name "github-actions[bot]"
           git add default.nix
           git commit -s -m "Update vendorSha256"
-          git push origin HEAD:${{ github.head_ref }}
+          git push origin HEAD:${{ github.head_ref }} 
 
 
       - name: Run build retry

diff --git a/go.mod b/go.mod
@@ -6,7 +6,6 @@ require (
 	github.com/Lochnair/go-patricia v2.3.3+incompatible
 	github.com/florianl/go-nfqueue v1.3.1
 	github.com/google/go-cmp v0.6.0
-	github.com/shomali11/util v0.0.0-20200329021417-91c54758c87b
 	golang.org/x/crypto v0.14.0
 )
 

diff --git a/go.sum b/go.sum
@@ -1,7 +1,5 @@
 github.com/Lochnair/go-patricia v2.3.3+incompatible h1:9O8xpwh39gpDb8NaOsznx2VdJIGSNrCSYzIFEgTfNdY=
 github.com/Lochnair/go-patricia v2.3.3+incompatible/go.mod h1:4smCwhlAYFuBu0hWsZOF4+0tdvay2zflyV+hoR0XNGQ=
-github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
-github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/florianl/go-nfqueue v1.3.1 h1:khQ9fYCrjbu5CF8dZF55G2RTIEIQRI0Aj5k3msJR6Gw=
 github.com/florianl/go-nfqueue v1.3.1/go.mod h1:aHWbgkhryJxF5XxYvJ3oRZpdD4JP74Zu/hP1zuhja+M=
 github.com/google/go-cmp v0.5.6/go.mod h1:v8dTdLbMG2kIc/vJvl+f65V22dbkXbowE6jgT/gNBxE=
@@ -16,13 +14,6 @@ github.com/mdlayher/socket v0.1.1 h1:q3uOGirUPfAV2MUoaC7BavjQ154J7+JOkTWyiV+intI
 github.com/mdlayher/socket v0.1.1/go.mod h1:mYV5YIZAfHh4dzDVzI8x8tWLWCliuX8Mon5Awbj+qDs=
 github.com/pkg/errors v0.9.1 h1:FEBLx1zS214owpjy7qsBeixbURkuhQAwrK5UwLGTwt4=
 github.com/pkg/errors v0.9.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
-github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
-github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
-github.com/shomali11/parallelizer v0.0.0-20180607005021-e11813c22f20/go.mod h1:HjzvRHgN5PGptIqjrdutIoZq4uCAemBTm/bGgnNLGiY=
-github.com/shomali11/util v0.0.0-20200329021417-91c54758c87b h1:vtWV9/bCF2tgRxv1R/tEENMwJaR8bXNhUimLMSUMVXw=
-github.com/shomali11/util v0.0.0-20200329021417-91c54758c87b/go.mod h1:89COV+EXrLrwQBk6nTUtYS5qVvTa2R0UMWSvUpHaX0Y=
-github.com/stretchr/testify v1.2.1 h1:52QO5WkIUcHGIR7EnGagH88x1bUzqGXTC5/1bDTUQ7U=
-github.com/stretchr/testify v1.2.1/go.mod h1:a8OnRcib4nhh0OaRAV+Yts87kKdq0PP7pXfy6kDkUVs=
 golang.org/x/crypto v0.14.0 h1:wBqGXzWJW6m1XrIKlAH0Hs1JJ7+9KBwnIO8v66Q9cHc=
 golang.org/x/crypto v0.14.0/go.mod h1:MVFd36DqK4CsrnJYDkBA3VC4m2GkXAM0PvzMCn4JQf4=
 golang.org/x/net v0.0.0-20210928044308-7d9f5e0b762b/go.mod h1:9nx3DQGgdP8bBQD5qxJ1jj9UTztislL4KSBs9R2vV5Y=

diff --git a/internal/tree/tree.go b/internal/tree/tree.go
@@ -1,8 +1,9 @@
 package tree
 
 import (
+	"unicode"
+
 	"github.com/Lochnair/go-patricia/patricia"
-	"github.com/shomali11/util/xstrings"
 )
 
 type Tree struct {
@@ -23,7 +24,7 @@ func (t *Tree) Match(domainName string) bool {
 	if len(domainName) < 1 {
 		return false
 	}
-	reversedDomain := xstrings.Reverse(domainName)
+	reversedDomain := Reverse(domainName)
 	_, _, found, leftover := t.domainTrie.FindSubtree(patricia.Prefix(reversedDomain))
 
 	/*
@@ -35,9 +36,48 @@ func (t *Tree) Match(domainName string) bool {
 
 func (t *Tree) Append(list []string) *Tree {
 	for _, domain := range list {
-		reversedDomain := xstrings.Reverse(domain)
+		reversedDomain := Reverse(domain)
 		t.domainTrie.Insert(patricia.Prefix(reversedDomain), 0)
 		t.size++
 	}
 	return t
 }
+
+// Reverse reverses the input while respecting UTF8 encoding and combined characters
+func Reverse(text string) string {
+	textRunes := []rune(text)
+	textRunesLength := len(textRunes)
+	if textRunesLength <= 1 {
+		return text
+	}
+
+	i, j := 0, 0
+	for i < textRunesLength && j < textRunesLength {
+		j = i + 1
+		for j < textRunesLength && IsMark(textRunes[j]) {
+			j++
+		}
+
+		if IsMark(textRunes[j-1]) {
+			// Reverses Combined Characters
+			reverse(textRunes[i:j], j-i)
+		}
+
+		i = j
+	}
+
+	// Reverses the entire array
+	reverse(textRunes, textRunesLength)
+
+	return string(textRunes)
+}
+
+func IsMark(r rune) bool {
+	return unicode.Is(unicode.Mn, r) || unicode.Is(unicode.Me, r) || unicode.Is(unicode.Mc, r)
+}
+
+func reverse(runes []rune, length int) {
+	for i, j := 0, length-1; i < length/2; i, j = i+1, j-1 {
+		runes[i], runes[j] = runes[j], runes[i]
+	}
+}