1-- Comparison evidence shared by every module that compares, hashes or
2-- orders its items: the map, the sort and the text layer import it, and
3-- a later type declares its conformances against it.
4
5--- Equality evidence. `equal` must be an equivalence relation, and stay one
6--- while an item is stored, for example as a map key.
7public equatable: type = concept (item: type)
8 --- Report whether two items are equal under a stable equivalence.
9 equal: (left: item, right: item) -> (yes: bool)
10end equatable
11
12--- Hash evidence composing `equatable`. Items that are `equal` must have
13--- equal hashes, and both must stay stable while an item is stored. Hashes
14--- are not cryptographic.
15---
16--- A hashable conformance composes equatable, but [1340] still requires a
17--- concrete type to declare both conformances explicitly.
18public hashable: type = concept (item: type) is equatable
19 --- Return a stable hash; items `equal` to each other hash equally.
20 hash: (value: item) -> (result: u64)
21end hashable
22
23-- The compiler does not prove the semantic laws: equal must be an
24-- equivalence relation, equal items must hash alike, and both answers must
25-- stay stable while an item is stored, including across mutation of
26-- anything a pointer or reference item reaches.
27
28-- Types the library supplies evidence for: the integer scalars, bool and
29-- byte slices here, and utf8 in core/text. There is one register and no
30-- override [1280]; a program wanting another equality or hash for one of
31-- these wraps the type in a distinct type and declares evidence for that.
32-- Signed hashes are the two's-complement bits widened, computed without
33-- a narrowing conversion; byte slices use 64-bit FNV-1a.
34equal_u8: (left: u8, right: u8) -> (yes: bool) =
35 yes = left == right
36end equal_u8
37hash_u8: (value: u8) -> (result: u64) =
38 result = u64(value)
39end hash_u8
40equal_u16: (left: u16, right: u16) -> (yes: bool) =
41 yes = left == right
42end equal_u16
43hash_u16: (value: u16) -> (result: u64) =
44 result = u64(value)
45end hash_u16
46equal_u32: (left: u32, right: u32) -> (yes: bool) =
47 yes = left == right
48end equal_u32
49hash_u32: (value: u32) -> (result: u64) =
50 result = u64(value)
51end hash_u32
52equal_u64: (left: u64, right: u64) -> (yes: bool) =
53 yes = left == right
54end equal_u64
55hash_u64: (value: u64) -> (result: u64) =
56 result = u64(value)
57end hash_u64
58equal_usize: (left: usize, right: usize) -> (yes: bool) =
59 yes = left == right
60end equal_usize
61hash_usize: (value: usize) -> (result: u64) =
62 result = u64(value)
63end hash_usize
64equal_i8: (left: i8, right: i8) -> (yes: bool) =
65 yes = left == right
66end equal_i8
67hash_i8: (value: i8) -> (result: u64) =
68 if value >= 0 then
69 result = u64(value)
70 else
71 result = ~u64(0 - (value + 1))
72 end if
73end hash_i8
74equal_i16: (left: i16, right: i16) -> (yes: bool) =
75 yes = left == right
76end equal_i16
77hash_i16: (value: i16) -> (result: u64) =
78 if value >= 0 then
79 result = u64(value)
80 else
81 result = ~u64(0 - (value + 1))
82 end if
83end hash_i16
84equal_i32: (left: i32, right: i32) -> (yes: bool) =
85 yes = left == right
86end equal_i32
87hash_i32: (value: i32) -> (result: u64) =
88 if value >= 0 then
89 result = u64(value)
90 else
91 result = ~u64(0 - (value + 1))
92 end if
93end hash_i32
94equal_i64: (left: i64, right: i64) -> (yes: bool) =
95 yes = left == right
96end equal_i64
97hash_i64: (value: i64) -> (result: u64) =
98 if value >= 0 then
99 result = u64(value)
100 else
101 result = ~u64(0 - (value + 1))
102 end if
103end hash_i64
104equal_isize: (left: isize, right: isize) -> (yes: bool) =
105 yes = left == right
106end equal_isize
107hash_isize: (value: isize) -> (result: u64) =
108 if value >= 0 then
109 result = u64(value)
110 else
111 result = ~u64(0 - (value + 1))
112 end if
113end hash_isize
114equal_bool: (left: bool, right: bool) -> (yes: bool) =
115 yes = left == right
116end equal_bool
117hash_bool: (value: bool) -> (result: u64) =
118 result = if value then 1 else 0 end if
119end hash_bool
120equal_bytes: (left: []u8, right: []u8) -> (yes: bool) =
121 if lenof left <> lenof right then
122 yes = false
123 return
124 end if
125 mut index: usize = 0
126 while index < lenof left do
127 if left[index] <> right[index] then
128 yes = false
129 return
130 end if
131 inc index
132 end while
133 yes = true
134end equal_bytes
135hash_bytes: (value: []u8) -> (result: u64) =
136 mut hash: u64 = 14695981039346656037
137 mut index: usize = 0
138 while index < lenof value do
139 hash = (hash ^ u64(value[index])) *% 1099511628211
140 inc index
141 end while
142 result = hash
143end hash_bytes
144u8 is equatable (equal: equal_u8)
145u8 is hashable (hash: hash_u8)
146u16 is equatable (equal: equal_u16)
147u16 is hashable (hash: hash_u16)
148u32 is equatable (equal: equal_u32)
149u32 is hashable (hash: hash_u32)
150u64 is equatable (equal: equal_u64)
151u64 is hashable (hash: hash_u64)
152usize is equatable (equal: equal_usize)
153usize is hashable (hash: hash_usize)
154i8 is equatable (equal: equal_i8)
155i8 is hashable (hash: hash_i8)
156i16 is equatable (equal: equal_i16)
157i16 is hashable (hash: hash_i16)
158i32 is equatable (equal: equal_i32)
159i32 is hashable (hash: hash_i32)
160i64 is equatable (equal: equal_i64)
161i64 is hashable (hash: hash_i64)
162isize is equatable (equal: equal_isize)
163isize is hashable (hash: hash_isize)
164bool is equatable (equal: equal_bool)
165bool is hashable (hash: hash_bool)
166[]u8 is equatable (equal: equal_bytes)
167[]u8 is hashable (hash: hash_bytes)
168
169--- Strict ordering evidence. `less` must be irreflexive and transitive, with
170--- consistent equivalence classes, for the duration of a sort.
171public ordered: type = concept (item: type)
172 --- Return true exactly when left precedes right under the strict weak
173 --- ordering.
174 less: (left: item, right: item) -> (yes: bool)
175end ordered
176
177-- The library supplies the ordering of every integer scalar, and core/text
178-- that of utf8. One register, no override [1280]: another ordering for one
179-- of these goes on a distinct wrapper.
180less_u8: (left: u8, right: u8) -> (yes: bool) =
181 yes = left < right
182end less_u8
183less_u16: (left: u16, right: u16) -> (yes: bool) =
184 yes = left < right
185end less_u16
186less_u32: (left: u32, right: u32) -> (yes: bool) =
187 yes = left < right
188end less_u32
189less_u64: (left: u64, right: u64) -> (yes: bool) =
190 yes = left < right
191end less_u64
192less_usize: (left: usize, right: usize) -> (yes: bool) =
193 yes = left < right
194end less_usize
195less_i8: (left: i8, right: i8) -> (yes: bool) =
196 yes = left < right
197end less_i8
198less_i16: (left: i16, right: i16) -> (yes: bool) =
199 yes = left < right
200end less_i16
201less_i32: (left: i32, right: i32) -> (yes: bool) =
202 yes = left < right
203end less_i32
204less_i64: (left: i64, right: i64) -> (yes: bool) =
205 yes = left < right
206end less_i64
207less_isize: (left: isize, right: isize) -> (yes: bool) =
208 yes = left < right
209end less_isize
210u8 is ordered (less: less_u8)
211u16 is ordered (less: less_u16)
212u32 is ordered (less: less_u32)
213u64 is ordered (less: less_u64)
214usize is ordered (less: less_usize)
215i8 is ordered (less: less_i8)
216i16 is ordered (less: less_i16)
217i32 is ordered (less: less_i32)
218i64 is ordered (less: less_i64)
219isize is ordered (less: less_isize)