1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
/*
* Copyright 2023 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef wasm_analysis_lattices_vector_h
#define wasm_analysis_lattices_vector_h
#include <vector>
#include "../lattice.h"
#include "bool.h"
#include "flat.h"
namespace wasm::analysis {
// A lattice whose elements are N-tuples of elements of L. Also written as L^N.
// N is supplied at run time rather than compile time like it is for Array.
template<Lattice L> struct Vector {
using Element = std::vector<typename L::Element>;
L lattice;
const size_t size;
Vector(L&& lattice, size_t size) : lattice(std::move(lattice)), size(size) {}
Element getBottom() const noexcept {
return Element(size, lattice.getBottom());
}
Element getTop() const noexcept
#if __cplusplus >= 202002L
requires FullLattice<L>
#endif
{
return Element(size, lattice.getTop());
}
// `a` <= `b` if their elements are pairwise <=, etc. Unless we determine
// that there is no relation, we must check all the elements.
LatticeComparison compare(const Element& a, const Element& b) const noexcept {
assert(a.size() == size);
assert(b.size() == size);
auto result = EQUAL;
for (size_t i = 0; i < size; ++i) {
switch (lattice.compare(a[i], b[i])) {
case NO_RELATION:
return NO_RELATION;
case EQUAL:
continue;
case LESS:
if (result == GREATER) {
// Cannot be both less and greater.
return NO_RELATION;
}
result = LESS;
continue;
case GREATER:
if (result == LESS) {
// Cannot be both greater and less.
return NO_RELATION;
}
result = GREATER;
continue;
}
}
return result;
}
// Pairwise join on the elements.
bool join(Element& joinee, const Element& joiner) const noexcept {
assert(joinee.size() == size);
assert(joiner.size() == size);
bool result = false;
for (size_t i = 0; i < size; ++i) {
if constexpr (std::is_same_v<typename L::Element, bool>) {
// The vector<bool> specialization does not expose references to the
// individual bools because they might be in a bitmap, so we need a
// workaround.
bool e = joinee[i];
if (lattice.join(e, joiner[i])) {
joinee[i] = e;
result = true;
}
} else {
result |= lattice.join(joinee[i], joiner[i]);
}
}
return result;
}
// Pairwise meet on the elements.
bool meet(Element& meetee, const Element& meeter) const noexcept
#if __cplusplus >= 202002L
requires FullLattice<L>
#endif
{
assert(meetee.size() == size);
assert(meeter.size() == size);
bool result = false;
for (size_t i = 0; i < size; ++i) {
if constexpr (std::is_same_v<typename L::Element, bool>) {
// The vector<bool> specialization does not expose references to the
// individual bools because they might be in a bitmap, so we need a
// workaround.
bool e = meetee[i];
if (lattice.meet(e, meeter[i])) {
meetee[i] = e;
result = true;
}
} else {
result |= lattice.meet(meetee[i], meeter[i]);
}
}
return result;
}
};
#if __cplusplus >= 202002L
static_assert(FullLattice<Vector<Bool>>);
static_assert(Lattice<Vector<Flat<bool>>>);
#endif
} // namespace wasm::analysis
#endif // wasm_analysis_lattices_vector_h
|
