Skip to content

Commit c830b8a

Browse files
wwqgtxxwwqgtxx
committed
feat: support convert mrs format back to text format
1 parent 1db3e45 commit c830b8a

10 files changed

+137
-12
lines changed

‎component/cidr/ipcidr_set.go

+10
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,16 @@ func (set *IpCidrSet) Merge() error {
5757
return nil
5858
}
5959

60+
func (set *IpCidrSet) Foreach(f func(prefix netip.Prefix) bool) {
61+
for _, r := range set.rr {
62+
for _, prefix := range r.Prefixes() {
63+
if !f(prefix) {
64+
return
65+
}
66+
}
67+
}
68+
}
69+
6070
// ToIPSet not safe convert to *netipx.IPSet
6171
// be careful, must be used after Merge
6272
func (set *IpCidrSet) ToIPSet() *netipx.IPSet {

‎component/trie/domain.go

+13-6
Original file line numberDiff line numberDiff line change
@@ -123,27 +123,34 @@ func (t *DomainTrie[T]) Optimize() {
123123
t.root.optimize()
124124
}
125125

126-
func (t *DomainTrie[T]) Foreach(print func(domain string, data T)) {
126+
func (t *DomainTrie[T]) Foreach(fn func(domain string, data T) bool) {
127127
for key, data := range t.root.getChildren() {
128-
recursion([]string{key}, data, print)
128+
recursion([]string{key}, data, fn)
129129
if data != nil && data.inited {
130-
print(joinDomain([]string{key}), data.data)
130+
if !fn(joinDomain([]string{key}), data.data) {
131+
return
132+
}
131133
}
132134
}
133135
}
134136

135-
func recursion[T any](items []string, node *Node[T], fn func(domain string, data T)) {
137+
func recursion[T any](items []string, node *Node[T], fn func(domain string, data T) bool) bool {
136138
for key, data := range node.getChildren() {
137139
newItems := append([]string{key}, items...)
138140
if data != nil && data.inited {
139141
domain := joinDomain(newItems)
140142
if domain[0] == domainStepByte {
141143
domain = complexWildcard + domain
142144
}
143-
fn(domain, data.Data())
145+
if !fn(domain, data.Data()) {
146+
return false
147+
}
148+
}
149+
if !recursion(newItems, data, fn) {
150+
return false
144151
}
145-
recursion(newItems, data, fn)
146152
}
153+
return true
147154
}
148155

149156
func joinDomain(items []string) string {

‎component/trie/domain_set.go

+37-1
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,9 @@ type qElt struct{ s, e, col int }
2828
// NewDomainSet creates a new *DomainSet struct, from a DomainTrie.
2929
func (t *DomainTrie[T]) NewDomainSet() *DomainSet {
3030
reserveDomains := make([]string, 0)
31-
t.Foreach(func(domain string, data T) {
31+
t.Foreach(func(domain string, data T) bool {
3232
reserveDomains = append(reserveDomains, utils.Reverse(domain))
33+
return true
3334
})
3435
// ensure that the same prefix is continuous
3536
// and according to the ascending sequence of length
@@ -136,6 +137,41 @@ func (ss *DomainSet) Has(key string) bool {
136137

137138
}
138139

140+
func (ss *DomainSet) keys(f func(key string) bool) {
141+
var currentKey []byte
142+
var traverse func(int, int) bool
143+
traverse = func(nodeId, bmIdx int) bool {
144+
if getBit(ss.leaves, nodeId) != 0 {
145+
if !f(string(currentKey)) {
146+
return false
147+
}
148+
}
149+
150+
for ; ; bmIdx++ {
151+
if getBit(ss.labelBitmap, bmIdx) != 0 {
152+
return true
153+
}
154+
nextLabel := ss.labels[bmIdx-nodeId]
155+
currentKey = append(currentKey, nextLabel)
156+
nextNodeId := countZeros(ss.labelBitmap, ss.ranks, bmIdx+1)
157+
nextBmIdx := selectIthOne(ss.labelBitmap, ss.ranks, ss.selects, nextNodeId-1) + 1
158+
if !traverse(nextNodeId, nextBmIdx) {
159+
return false
160+
}
161+
currentKey = currentKey[:len(currentKey)-1]
162+
}
163+
}
164+
165+
traverse(0, 0)
166+
return
167+
}
168+
169+
func (ss *DomainSet) Foreach(f func(key string) bool) {
170+
ss.keys(func(key string) bool {
171+
return f(utils.Reverse(key))
172+
})
173+
}
174+
139175
func setBit(bm *[]uint64, i int, v int) {
140176
for i>>6 >= len(*bm) {
141177
*bm = append(*bm, 0)

‎component/trie/domain_set_test.go

+20
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,29 @@
11
package trie_test
22

33
import (
4+
"golang.org/x/exp/slices"
45
"testing"
56

67
"github.com/metacubex/mihomo/component/trie"
78
"github.com/stretchr/testify/assert"
89
)
910

11+
func testDump(t *testing.T, tree *trie.DomainTrie[struct{}], set *trie.DomainSet) {
12+
var dataSrc []string
13+
tree.Foreach(func(domain string, data struct{}) bool {
14+
dataSrc = append(dataSrc, domain)
15+
return true
16+
})
17+
slices.Sort(dataSrc)
18+
var dataSet []string
19+
set.Foreach(func(key string) bool {
20+
dataSet = append(dataSet, key)
21+
return true
22+
})
23+
slices.Sort(dataSet)
24+
assert.Equal(t, dataSrc, dataSet)
25+
}
26+
1027
func TestDomainSet(t *testing.T) {
1128
tree := trie.New[struct{}]()
1229
domainSet := []string{
@@ -33,6 +50,7 @@ func TestDomainSet(t *testing.T) {
3350
assert.True(t, set.Has("google.com"))
3451
assert.False(t, set.Has("qq.com"))
3552
assert.False(t, set.Has("www.baidu.com"))
53+
testDump(t, tree, set)
3654
}
3755

3856
func TestDomainSetComplexWildcard(t *testing.T) {
@@ -55,6 +73,7 @@ func TestDomainSetComplexWildcard(t *testing.T) {
5573
assert.False(t, set.Has("google.com"))
5674
assert.True(t, set.Has("www.baidu.com"))
5775
assert.True(t, set.Has("test.test.baidu.com"))
76+
testDump(t, tree, set)
5877
}
5978

6079
func TestDomainSetWildcard(t *testing.T) {
@@ -82,4 +101,5 @@ func TestDomainSetWildcard(t *testing.T) {
82101
assert.False(t, set.Has("a.www.google.com"))
83102
assert.False(t, set.Has("test.qq.com"))
84103
assert.False(t, set.Has("test.test.test.qq.com"))
104+
testDump(t, tree, set)
85105
}

‎component/trie/domain_test.go

+2-1
Original file line numberDiff line numberDiff line change
@@ -121,8 +121,9 @@ func TestTrie_Foreach(t *testing.T) {
121121
assert.NoError(t, tree.Insert(domain, localIP))
122122
}
123123
count := 0
124-
tree.Foreach(func(domain string, data netip.Addr) {
124+
tree.Foreach(func(domain string, data netip.Addr) bool {
125125
count++
126+
return true
126127
})
127128
assert.Equal(t, 7, count)
128129
}

‎docs/config.yaml

+11-4
Original file line numberDiff line numberDiff line change
@@ -944,10 +944,17 @@ rule-providers:
944944
type: file
945945
rule3:
946946
# mrs类型ruleset，目前仅支持domain和ipcidr(即不支持classical），
947-
# behavior=domain,format=yaml 可以通过“mihomo convert-ruleset domain yaml XXX.yaml XXX.mrs”转换得到
948-
# behavior=domain,format=text 可以通过“mihomo convert-ruleset domain text XXX.text XXX.mrs”转换得到
949-
# behavior=ipcidr,format=yaml 可以通过“mihomo convert-ruleset ipcidr yaml XXX.yaml XXX.mrs”转换得到
950-
# behavior=ipcidr,format=text 可以通过“mihomo convert-ruleset ipcidr text XXX.text XXX.mrs”转换得到
947+
#
948+
# 对于behavior=domain:
949+
# - format=yaml 可以通过“mihomo convert-ruleset domain yaml XXX.yaml XXX.mrs”转换到mrs格式
950+
# - format=text 可以通过“mihomo convert-ruleset domain text XXX.text XXX.mrs”转换到mrs格式
951+
# - XXX.mrs 可以通过"mihomo convert-ruleset domain mrs XXX.mrs XXX.text"转换回text格式（暂不支持转换回ymal格式）
952+
#
953+
# 对于behavior=ipcidr:
954+
# - format=yaml 可以通过“mihomo convert-ruleset ipcidr yaml XXX.yaml XXX.mrs”转换到mrs格式
955+
# - format=text 可以通过“mihomo convert-ruleset ipcidr text XXX.text XXX.mrs”转换到mrs格式
956+
# - XXX.mrs 可以通过"mihomo convert-ruleset ipcidr mrs XXX.mrs XXX.text"转换回text格式（暂不支持转换回ymal格式）
957+
#
951958
type: http
952959
url: "url"
953960
format: mrs

‎rules/provider/domain_strategy.go

+22
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,8 @@ import (
99
C "github.com/metacubex/mihomo/constant"
1010
P "github.com/metacubex/mihomo/constant/provider"
1111
"github.com/metacubex/mihomo/log"
12+
13+
"golang.org/x/exp/slices"
1214
)
1315

1416
type domainStrategy struct {
@@ -78,6 +80,26 @@ func (d *domainStrategy) WriteMrs(w io.Writer) error {
7880
return d.domainSet.WriteBin(w)
7981
}
8082

83+
func (d *domainStrategy) DumpMrs(f func(key string) bool) {
84+
if d.domainSet != nil {
85+
var keys []string
86+
d.domainSet.Foreach(func(key string) bool {
87+
keys = append(keys, key)
88+
return true
89+
})
90+
slices.Sort(keys)
91+
92+
for _, key := range keys {
93+
if _, ok := slices.BinarySearch(keys, "+."+key); ok {
94+
continue // ignore the rules added by trie internal processing
95+
}
96+
if !f(key) {
97+
return
98+
}
99+
}
100+
}
101+
}
102+
81103
var _ mrsRuleStrategy = (*domainStrategy)(nil)
82104

83105
func NewDomainStrategy() *domainStrategy {

‎rules/provider/ipcidr_strategy.go

+9
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@ package provider
33
import (
44
"errors"
55
"io"
6+
"net/netip"
67

78
"github.com/metacubex/mihomo/component/cidr"
89
C "github.com/metacubex/mihomo/constant"
@@ -82,6 +83,14 @@ func (i *ipcidrStrategy) WriteMrs(w io.Writer) error {
8283
return i.cidrSet.WriteBin(w)
8384
}
8485

86+
func (i *ipcidrStrategy) DumpMrs(f func(key string) bool) {
87+
if i.cidrSet != nil {
88+
i.cidrSet.Foreach(func(prefix netip.Prefix) bool {
89+
return f(prefix.String())
90+
})
91+
}
92+
}
93+
8594
func (i *ipcidrStrategy) ToIpCidr() *netipx.IPSet {
8695
return i.cidrSet.ToIPSet()
8796
}

‎rules/provider/mrs_converter.go

+12
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@ package provider
33
import (
44
"encoding/binary"
55
"errors"
6+
"fmt"
67
"io"
78
"os"
89

@@ -21,6 +22,17 @@ func ConvertToMrs(buf []byte, behavior P.RuleBehavior, format P.RuleFormat, w io
2122
return errors.New("empty rule")
2223
}
2324
if _strategy, ok := strategy.(mrsRuleStrategy); ok {
25+
if format == P.MrsRule { // export to TextRule
26+
_strategy.DumpMrs(func(key string) bool {
27+
_, err = fmt.Fprintln(w, key)
28+
if err != nil {
29+
return false
30+
}
31+
return true
32+
})
33+
return nil
34+
}
35+
2436
var encoder *zstd.Encoder
2537
encoder, err = zstd.NewWriter(w)
2638
if err != nil {

‎rules/provider/provider.go

+1
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@ type mrsRuleStrategy interface {
5858
ruleStrategy
5959
FromMrs(r io.Reader, count int) error
6060
WriteMrs(w io.Writer) error
61+
DumpMrs(f func(key string) bool)
6162
}
6263

6364
func (rp *ruleSetProvider) Type() P.ProviderType {

0 commit comments

Comments
 (0)