Skip to content

Commit cb295d4

Browse files
jakobmoellerdevjakobmoellerdev
authored
fix: make sure prototypes can be used for reregistration (#1284)
<!-- markdownlint-disable MD041 --> #### What this PR does / why we need it Previously, in the scheme we did not store by Prototype but by type. Because the scheme did not key by Prototype, one could register multiple defaults with the same underlying prototype value. However, this is incorrect. Instead there should be only one prototype instance at any given time in a scheme. If there are multiple registrations happening in succession, the prototype should still stay atomic, and all calls should instead only append to the aliases #### Which issue(s) this PR fixes <!-- Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`. --> was discovered as part of scheme debugging in e25a7d0 --------- Signed-off-by: Jakob Möller <contact@jakob-moeller.com>
1 parent da3649c commit cb295d4

5 files changed

Lines changed: 368 additions & 86 deletions

File tree

‎bindings/go/runtime/internal/bimap/bimap.go‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
// Package bimap provides a compact bidirectional map implementation
2+
// with O(1) lookup from left→right and right→left.
3+
// Values are stored only once internally.
4+
package bimap
5+
6+
import "iter"
7+
8+
// Map is a bidirectional mapping between a Left and Right value.
9+
// Each Left maps to exactly one Right and vice-versa.
10+
type Map[L, R comparable] struct {
11+
pairs []pair[L, R]
12+
index index[L, R]
13+
}
14+
15+
type index[L, R comparable] struct {
16+
left map[L]int
17+
right map[R]int
18+
}
19+
20+
type pair[L, R comparable] struct {
21+
left L
22+
right R
23+
}
24+
25+
// New creates an empty Map.
26+
// Both directions support O(1) lookup.
27+
func New[L, R comparable]() *Map[L, R] {
28+
return &Map[L, R]{
29+
index: index[L, R]{left: make(map[L]int), right: make(map[R]int)},
30+
}
31+
}
32+
33+
// Set inserts or updates the mapping for left↔right.
34+
// If left already exists, its old right mapping is replaced.
35+
// If right already exists, its old left mapping is replaced.
36+
// If neither exists, a new pair is appended.
37+
// Exactly one final mapping per left and right is maintained.
38+
func (m *Map[L, R]) Set(left L, right R) {
39+
if i, ok := m.index.left[left]; ok {
40+
delete(m.index.right, m.pairs[i].right)
41+
m.pairs[i].right = right
42+
m.index.right[right] = i
43+
return
44+
}
45+
if i, ok := m.index.right[right]; ok {
46+
delete(m.index.left, m.pairs[i].left)
47+
m.pairs[i].left = left
48+
m.index.left[left] = i
49+
return
50+
}
51+
i := len(m.pairs)
52+
m.pairs = append(m.pairs, pair[L, R]{left, right})
53+
m.index.left[left] = i
54+
m.index.right[right] = i
55+
}
56+
57+
// GetLeft returns the Right value associated with l.
58+
// The boolean indicates whether the mapping exists.
59+
func (m *Map[L, R]) GetLeft(l L) (R, bool) {
60+
i, ok := m.index.left[l]
61+
if ok {
62+
return m.pairs[i].right, true
63+
}
64+
var zero R
65+
return zero, false
66+
}
67+
68+
// GetRight returns the Left value associated with r.
69+
// The boolean indicates whether the mapping exists.
70+
func (m *Map[L, R]) GetRight(r R) (L, bool) {
71+
i, ok := m.index.right[r]
72+
if ok {
73+
return m.pairs[i].left, true
74+
}
75+
var zero L
76+
return zero, false
77+
}
78+
79+
// Len returns the number of stored left↔right mappings.
80+
func (m *Map[L, R]) Len() int {
81+
return len(m.pairs)
82+
}
83+
84+
// Iter returns an iterator over all (left, right) pairs.
85+
// Iteration order is stable based on insertion/update order.
86+
func (m *Map[L, R]) Iter() iter.Seq2[L, R] {
87+
return func(yield func(L, R) bool) {
88+
for _, pair := range m.pairs {
89+
if !yield(pair.left, pair.right) {
90+
return
91+
}
92+
}
93+
}
94+
}
95+
96+
// Clone returns a deep copy of the Map,
97+
// preserving all mappings while maintaining new internal storage.
98+
func (m *Map[L, R]) Clone() *Map[L, R] {
99+
clone := New[L, R]()
100+
for l, r := range m.Iter() {
101+
clone.Set(l, r)
102+
}
103+
return clone
104+
}

‎bindings/go/runtime/internal/bimap/bimap_test.go‎

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
package bimap_test
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/require"
7+
"ocm.software/open-component-model/bindings/go/runtime/internal/bimap"
8+
)
9+
10+
func TestSetAndGet(t *testing.T) {
11+
r := require.New(t)
12+
13+
m := bimap.New[string, int]()
14+
15+
m.Set("a", 1)
16+
m.Set("b", 2)
17+
18+
right, ok := m.GetLeft("a")
19+
r.True(ok)
20+
r.Equal(1, right)
21+
22+
left, ok := m.GetRight(2)
23+
r.True(ok)
24+
r.Equal("b", left)
25+
26+
r.Equal(2, m.Len())
27+
}
28+
29+
func TestOverwrite(t *testing.T) {
30+
t.Run("Left", func(t *testing.T) {
31+
r := require.New(t)
32+
33+
m := bimap.New[string, int]()
34+
35+
m.Set("a", 1)
36+
m.Set("a", 2) // overwrite right side of "a"
37+
38+
v, ok := m.GetLeft("a")
39+
r.True(ok)
40+
r.Equal(2, v)
41+
42+
_, ok = m.GetRight(1)
43+
r.False(ok)
44+
45+
l, ok := m.GetRight(2)
46+
r.True(ok)
47+
r.Equal("a", l)
48+
49+
r.Equal(1, m.Len())
50+
})
51+
52+
t.Run("Right", func(t *testing.T) {
53+
r := require.New(t)
54+
55+
m := bimap.New[string, int]()
56+
57+
m.Set("a", 1)
58+
m.Set("b", 1) // overwrite left side of right value 1
59+
60+
l, ok := m.GetRight(1)
61+
r.True(ok)
62+
r.Equal("b", l)
63+
64+
_, ok = m.GetLeft("a")
65+
r.False(ok)
66+
67+
v, ok := m.GetLeft("b")
68+
r.True(ok)
69+
r.Equal(1, v)
70+
71+
r.Equal(1, m.Len())
72+
})
73+
}
74+
75+
func TestIterOrder(t *testing.T) {
76+
r := require.New(t)
77+
78+
m := bimap.New[string, int]()
79+
80+
m.Set("a", 1)
81+
m.Set("b", 2)
82+
m.Set("c", 3)
83+
84+
var seen []struct {
85+
L string
86+
R int
87+
}
88+
89+
for l, v := range m.Iter() {
90+
seen = append(seen, struct {
91+
L string
92+
R int
93+
}{l, v})
94+
}
95+
96+
r.Equal([]struct {
97+
L string
98+
R int
99+
}{
100+
{"a", 1},
101+
{"b", 2},
102+
{"c", 3},
103+
}, seen)
104+
}
105+
106+
func TestClone(t *testing.T) {
107+
r := require.New(t)
108+
109+
m := bimap.New[string, int]()
110+
m.Set("a", 1)
111+
m.Set("b", 2)
112+
113+
clone := m.Clone()
114+
115+
// same content
116+
v, ok := clone.GetLeft("a")
117+
r.True(ok)
118+
r.Equal(1, v)
119+
120+
v, ok = clone.GetLeft("b")
121+
r.True(ok)
122+
r.Equal(2, v)
123+
124+
r.Equal(2, clone.Len())
125+
126+
// but independent storage
127+
m.Set("c", 3)
128+
r.Equal(3, m.Len())
129+
r.Equal(2, clone.Len())
130+
}
131+
132+
func TestGetMissing(t *testing.T) {
133+
r := require.New(t)
134+
135+
m := bimap.New[string, int]()
136+
137+
_, ok := m.GetLeft("missing-left")
138+
r.False(ok)
139+
140+
_, ok = m.GetRight(999)
141+
r.False(ok)
142+
}

0 commit comments

Comments
 (0)