Skip to content

Commit 6dac371

Browse files
xaionaro@dx.centerxaionaro@dx.center
[email protected]
authored and
[email protected]
committed
feat(versionaware): add CompiledTable type with sorted slices and binary search
1 parent eadc220 commit 6dac371

8 files changed

Lines changed: 338 additions & 42 deletions

File tree

‎binder/versionaware/codes_gen.go‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ import "github.com/AndroidGoLab/binder/binder"
66

77
func init() {
88
DefaultAPILevel = 36
9-
Tables = MultiVersionTable{
9+
rawTables := map[Revision]VersionTable{
1010
"34.r1": VersionTable{
1111
"aaudio.IAAudioClient": {
1212
"onStreamChange": binder.FirstCallTransaction + 0,
@@ -434415,6 +434415,7 @@ func init() {
434415434415
},
434416434416
},
434417434417
}
434418+
Tables = compileRawTables(rawTables)
434418434419
Revisions = APIRevisions{
434419434420
34: {"34.r75", "34.r74", "34.r67", "34.r66", "34.r62", "34.r50", "34.r38", "34.r29", "34.r28", "34.r19", "34.r16", "34.r13", "34.r11", "34.r3", "34.r1"},
434420434421
35: {"35.r32", "35.r31", "35.r26", "35.r24", "35.r23", "35.r20", "35.r6", "35.r1"},

‎binder/versionaware/compile_raw_tables.go‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package versionaware
2+
3+
import "sort"
4+
5+
// compileRawTables converts a map-based version table collection into
6+
// sorted CompiledTable slices suitable for binary search lookups.
7+
// Used by codes_gen.go to bridge the legacy VersionTable format
8+
// until the code generator emits CompiledTable literals directly.
9+
func compileRawTables(
10+
raw map[Revision]VersionTable,
11+
) MultiVersionTable {
12+
result := make(MultiVersionTable, len(raw))
13+
for rev, vt := range raw {
14+
result[rev] = compileVersionTable(vt)
15+
}
16+
return result
17+
}
18+
19+
// compileVersionTable converts a single VersionTable (map) into
20+
// a sorted CompiledTable (slice).
21+
func compileVersionTable(
22+
vt VersionTable,
23+
) CompiledTable {
24+
ct := make(CompiledTable, 0, len(vt))
25+
for descriptor, methods := range vt {
26+
entries := make([]MethodEntry, 0, len(methods))
27+
for method, code := range methods {
28+
entries = append(entries, MethodEntry{
29+
Method: method,
30+
Code: code,
31+
})
32+
}
33+
sort.Slice(entries, func(i, j int) bool {
34+
return entries[i].Method < entries[j].Method
35+
})
36+
ct = append(ct, InterfaceEntry{
37+
Descriptor: descriptor,
38+
Methods: entries,
39+
})
40+
}
41+
sort.Slice(ct, func(i, j int) bool {
42+
return ct[i].Descriptor < ct[j].Descriptor
43+
})
44+
return ct
45+
}

‎binder/versionaware/compiled_table.go‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
package versionaware
2+
3+
import (
4+
"sort"
5+
6+
"github.com/AndroidGoLab/binder/binder"
7+
)
8+
9+
// MethodEntry maps a method name to its transaction code.
10+
type MethodEntry struct {
11+
Method string
12+
Code binder.TransactionCode
13+
}
14+
15+
// InterfaceEntry maps a descriptor to its sorted method list.
16+
type InterfaceEntry struct {
17+
Descriptor string
18+
Methods []MethodEntry // sorted by Method
19+
}
20+
21+
// CompiledTable is a read-only table of transaction codes stored as
22+
// sorted slices for zero-cost initialization (no runtime hash table
23+
// construction). Use Resolve for lookups.
24+
type CompiledTable []InterfaceEntry // sorted by Descriptor
25+
26+
// Resolve looks up the transaction code for a method.
27+
// Returns 0 if not found. Uses binary search.
28+
func (t CompiledTable) Resolve(
29+
descriptor string,
30+
method string,
31+
) binder.TransactionCode {
32+
i := sort.Search(len(t), func(i int) bool {
33+
return t[i].Descriptor >= descriptor
34+
})
35+
if i >= len(t) || t[i].Descriptor != descriptor {
36+
return 0
37+
}
38+
methods := t[i].Methods
39+
j := sort.Search(len(methods), func(j int) bool {
40+
return methods[j].Method >= method
41+
})
42+
if j >= len(methods) || methods[j].Method != method {
43+
return 0
44+
}
45+
return methods[j].Code
46+
}
47+
48+
// ReverseResolve looks up the method name for a transaction code.
49+
// Returns ("", false) if not found.
50+
func (t CompiledTable) ReverseResolve(
51+
descriptor string,
52+
code binder.TransactionCode,
53+
) (string, bool) {
54+
i := sort.Search(len(t), func(i int) bool {
55+
return t[i].Descriptor >= descriptor
56+
})
57+
if i >= len(t) || t[i].Descriptor != descriptor {
58+
return "", false
59+
}
60+
for _, m := range t[i].Methods {
61+
if m.Code == code {
62+
return m.Method, true
63+
}
64+
}
65+
return "", false
66+
}
67+
68+
// HasDescriptor reports whether the table contains the given descriptor.
69+
func (t CompiledTable) HasDescriptor(descriptor string) bool {
70+
i := sort.Search(len(t), func(i int) bool {
71+
return t[i].Descriptor >= descriptor
72+
})
73+
return i < len(t) && t[i].Descriptor == descriptor
74+
}
75+
76+
// MethodsForDescriptor returns the method entries for a descriptor.
77+
// Returns nil if the descriptor is not found.
78+
func (t CompiledTable) MethodsForDescriptor(
79+
descriptor string,
80+
) []MethodEntry {
81+
i := sort.Search(len(t), func(i int) bool {
82+
return t[i].Descriptor >= descriptor
83+
})
84+
if i >= len(t) || t[i].Descriptor != descriptor {
85+
return nil
86+
}
87+
return t[i].Methods
88+
}
89+
90+
// ToVersionTable converts a compiled table to a mutable VersionTable.
91+
func (t CompiledTable) ToVersionTable() VersionTable {
92+
vt := make(VersionTable, len(t))
93+
for _, iface := range t {
94+
methods := make(map[string]binder.TransactionCode, len(iface.Methods))
95+
for _, m := range iface.Methods {
96+
methods[m.Method] = m.Code
97+
}
98+
vt[iface.Descriptor] = methods
99+
}
100+
return vt
101+
}
102+
103+
// IsSorted reports whether the table's invariants hold:
104+
// interfaces sorted by Descriptor (strictly increasing),
105+
// methods sorted by Method within each (strictly increasing).
106+
func (t CompiledTable) IsSorted() bool {
107+
for i := 1; i < len(t); i++ {
108+
if t[i].Descriptor <= t[i-1].Descriptor {
109+
return false
110+
}
111+
}
112+
for _, iface := range t {
113+
for j := 1; j < len(iface.Methods); j++ {
114+
if iface.Methods[j].Method <= iface.Methods[j-1].Method {
115+
return false
116+
}
117+
}
118+
}
119+
return true
120+
}

‎binder/versionaware/compiled_table_test.go‎

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
package versionaware
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/assert"
7+
"github.com/stretchr/testify/require"
8+
9+
"github.com/AndroidGoLab/binder/binder"
10+
)
11+
12+
func TestCompiledTable_Resolve(t *testing.T) {
13+
sorted := CompiledTable{
14+
{Descriptor: "android.app.IBar", Methods: []MethodEntry{
15+
{Method: "barMethod", Code: binder.FirstCallTransaction + 0},
16+
}},
17+
{Descriptor: "android.app.IFoo", Methods: []MethodEntry{
18+
{Method: "doOther", Code: binder.FirstCallTransaction + 1},
19+
{Method: "doThing", Code: binder.FirstCallTransaction + 0},
20+
}},
21+
}
22+
require.True(t, sorted.IsSorted())
23+
24+
assert.Equal(t, binder.FirstCallTransaction+0, sorted.Resolve("android.app.IFoo", "doThing"))
25+
assert.Equal(t, binder.FirstCallTransaction+1, sorted.Resolve("android.app.IFoo", "doOther"))
26+
assert.Equal(t, binder.FirstCallTransaction+0, sorted.Resolve("android.app.IBar", "barMethod"))
27+
assert.Equal(t, binder.TransactionCode(0), sorted.Resolve("android.app.IFoo", "nonExistent"))
28+
assert.Equal(t, binder.TransactionCode(0), sorted.Resolve("nonexistent.IFoo", "bar"))
29+
}
30+
31+
func TestCompiledTable_ReverseResolve(t *testing.T) {
32+
table := CompiledTable{
33+
{Descriptor: "android.app.IFoo", Methods: []MethodEntry{
34+
{Method: "doOther", Code: binder.FirstCallTransaction + 1},
35+
{Method: "doThing", Code: binder.FirstCallTransaction + 0},
36+
}},
37+
}
38+
39+
name, ok := table.ReverseResolve("android.app.IFoo", binder.FirstCallTransaction+1)
40+
assert.True(t, ok)
41+
assert.Equal(t, "doOther", name)
42+
43+
_, ok = table.ReverseResolve("android.app.IFoo", binder.FirstCallTransaction+99)
44+
assert.False(t, ok)
45+
46+
_, ok = table.ReverseResolve("nonexistent", binder.FirstCallTransaction+0)
47+
assert.False(t, ok)
48+
}
49+
50+
func TestCompiledTable_IsSorted(t *testing.T) {
51+
sorted := CompiledTable{
52+
{Descriptor: "aaa", Methods: []MethodEntry{
53+
{Method: "aMethod", Code: 1},
54+
{Method: "bMethod", Code: 2},
55+
}},
56+
{Descriptor: "bbb", Methods: []MethodEntry{
57+
{Method: "xMethod", Code: 1},
58+
}},
59+
}
60+
assert.True(t, sorted.IsSorted())
61+
62+
unsortedDesc := CompiledTable{
63+
{Descriptor: "bbb", Methods: nil},
64+
{Descriptor: "aaa", Methods: nil},
65+
}
66+
assert.False(t, unsortedDesc.IsSorted())
67+
68+
unsortedMethods := CompiledTable{
69+
{Descriptor: "aaa", Methods: []MethodEntry{
70+
{Method: "bMethod", Code: 2},
71+
{Method: "aMethod", Code: 1},
72+
}},
73+
}
74+
assert.False(t, unsortedMethods.IsSorted())
75+
76+
dupDesc := CompiledTable{
77+
{Descriptor: "aaa", Methods: nil},
78+
{Descriptor: "aaa", Methods: nil},
79+
}
80+
assert.False(t, dupDesc.IsSorted())
81+
}
82+
83+
func TestCompiledTable_ToVersionTable(t *testing.T) {
84+
ct := CompiledTable{
85+
{Descriptor: "android.app.IFoo", Methods: []MethodEntry{
86+
{Method: "doOther", Code: binder.FirstCallTransaction + 1},
87+
{Method: "doThing", Code: binder.FirstCallTransaction + 0},
88+
}},
89+
}
90+
vt := ct.ToVersionTable()
91+
assert.Equal(t, binder.FirstCallTransaction+0, vt["android.app.IFoo"]["doThing"])
92+
assert.Equal(t, binder.FirstCallTransaction+1, vt["android.app.IFoo"]["doOther"])
93+
}
94+
95+
func TestCompiledTable_HasDescriptor(t *testing.T) {
96+
ct := CompiledTable{
97+
{Descriptor: "android.app.IFoo", Methods: nil},
98+
}
99+
assert.True(t, ct.HasDescriptor("android.app.IFoo"))
100+
assert.False(t, ct.HasDescriptor("nonexistent"))
101+
}
102+
103+
func TestCompiledTable_MethodsForDescriptor(t *testing.T) {
104+
methods := []MethodEntry{
105+
{Method: "alpha", Code: 1},
106+
{Method: "beta", Code: 2},
107+
}
108+
ct := CompiledTable{
109+
{Descriptor: "android.app.IFoo", Methods: methods},
110+
}
111+
assert.Equal(t, methods, ct.MethodsForDescriptor("android.app.IFoo"))
112+
assert.Nil(t, ct.MethodsForDescriptor("nonexistent"))
113+
}
114+
115+
func TestTablesAreSorted(t *testing.T) {
116+
if len(Tables) == 0 {
117+
t.Skip("Tables not yet populated with CompiledTable data")
118+
}
119+
for rev, table := range Tables {
120+
if !table.IsSorted() {
121+
t.Errorf("Tables[%q] is not sorted", rev)
122+
}
123+
}
124+
}

‎binder/versionaware/multi_version_table.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
package versionaware
22

3-
// MultiVersionTable maps Revision -> VersionTable.
3+
// MultiVersionTable maps Revision -> CompiledTable.
44
// Revisions are like "34.r1", "35.r1", "36.r1", "36.r3", "36.r4".
5-
type MultiVersionTable map[Revision]VersionTable
5+
type MultiVersionTable map[Revision]CompiledTable

0 commit comments

Comments
 (0)