Branch data Line data Source code
1 : : #pragma once
2 : :
3 : : #include "backend/InterpreterOperator.hpp"
4 : : #include "backend/StackMachine.hpp"
5 : : #include <cerrno>
6 : : #include <ctime>
7 : : #include <mutable/backend/Backend.hpp>
8 : : #include <mutable/catalog/Catalog.hpp>
9 : : #include <mutable/IR/Operator.hpp>
10 : : #include <mutable/IR/Tuple.hpp>
11 : : #include <mutable/util/macro.hpp>
12 : : #include <unordered_map>
13 : :
14 : :
15 : : namespace m {
16 : :
17 : : /** A block of size `N` contains `N` tuples. */
18 : : template<std::size_t N>
19 : : struct Block
20 : : {
21 : : static constexpr std::size_t CAPACITY = N; ///< the capacity of a block
22 : :
23 : : private:
24 : : template<bool C>
25 : : struct the_iterator
26 : : {
27 : : static constexpr bool IsConst = C;
28 : :
29 : : using block_t = std::conditional_t<IsConst, const Block, Block>;
30 : : using reference = std::conditional_t<IsConst, const Tuple&, Tuple&>;
31 : : using pointer = std::conditional_t<IsConst, const Tuple*, Tuple*>;
32 : :
33 : : private:
34 : : block_t &block_;
35 : : uint64_t mask_;
36 : :
37 : : public:
38 : 4790 : the_iterator(block_t &vec, uint64_t mask) : block_(vec), mask_(mask) { }
39 : :
40 : 8920 : bool operator==(the_iterator other) {
41 : 8920 : M_insist(&this->block_ == &other.block_);
42 : 8920 : return this->mask_ == other.mask_;
43 : : }
44 : 8920 : bool operator!=(the_iterator other) { return not operator==(other); }
45 : :
46 : 8700 : the_iterator & operator++() { mask_ = mask_ & (mask_ - 1UL); /* set lowest 1-bit to 0 */ return *this; }
47 : : the_iterator operator++(int) { the_iterator clone(*this); operator++(); return clone; }
48 : :
49 : 13050 : std::size_t index() const { return __builtin_ctzl(mask_); }
50 : :
51 : 8700 : reference operator*() const { return block_[index()]; }
52 : : pointer operator->() const { return &block_[index()]; }
53 : : };
54 : :
55 : : public:
56 : : using iterator = the_iterator<false>;
57 : : using const_iterator = the_iterator<true>;
58 : :
59 : : private:
60 : : std::array<Tuple, N> data_; ///< an array of the tuples of this `Block`; some slots may be unused
61 : 162 : uint64_t mask_ = 0x0; ///< a mast identifying which slots of `data_` are in use
62 : : static_assert(N <= 64, "maximum block size exceeded");
63 : : Schema schema_;
64 : :
65 : : public:
66 : 0 : Block() = default;
67 : : Block(const Block&) = delete;
68 : : Block(Block&&) = delete;
69 : :
70 : : /** Create a new `Block` with tuples of `Schema` `schema`. */
71 : 162 : Block(Schema schema)
72 : 162 : : schema_(std::move(schema))
73 : : {
74 [ + + ]: 10530 : for (auto &t : data_)
75 [ + - + - ]: 10368 : t = Tuple(schema_);
76 : 162 : }
77 : :
78 : : /** Return a pointer to the underlying array of tuples. */
79 : : Tuple * data() { return data_.data(); }
80 : : /** Return a pointer to the underlying array of tuples. */
81 : : const Tuple * data() const { return data_.data(); }
82 : :
83 : 68 : const Schema & schema() const { return schema_; }
84 : :
85 : : /** Return the capacity of this `Block`. */
86 : 39399 : static constexpr std::size_t capacity() { return CAPACITY; }
87 : : /** Return the number of *alive* tuples in this `Block`. */
88 : 42 : std::size_t size() const { return __builtin_popcountl(mask_); }
89 : :
90 : 220 : iterator begin() { return iterator(*this, mask_); }
91 : 4570 : iterator end() { return iterator(*this, 0UL); }
92 : : const_iterator begin() const { return const_iterator(*this, mask_); }
93 : : const_iterator end() const { return const_iterator(*this, 0UL); }
94 : : const_iterator cbegin() const { return const_iterator(*this, mask_); }
95 : : const_iterator cend() const { return const_iterator(*this, 0UL); }
96 : :
97 : : /** Returns an iterator to the tuple at index `index`. */
98 : : iterator at(std::size_t index) {
99 : : M_insist(index < capacity());
100 : : return iterator(*this, mask_ & (-1UL << index));
101 : : }
102 : : /** Returns an iterator to the tuple at index `index`. */
103 : : const_iterator at(std::size_t index) const { return const_cast<Block>(this)->at(index); }
104 : :
105 : : /** Check whether the tuple at the given `index` is alive. */
106 : 17400 : bool alive(std::size_t index) const {
107 : 17400 : M_insist(index < capacity());
108 : 17400 : return mask_ & (1UL << index);
109 : : }
110 : :
111 : : /** Returns `true` iff the block has no *alive* tuples, i.e.\ `size() == 0`. */
112 : 0 : bool empty() const { return size() == 0; }
113 : :
114 : : /** Returns the bit mask that identifies which tuples of this `Block` are alive. */
115 : 110 : uint64_t mask() const { return mask_; }
116 : : /** Returns the bit mask that identifies which tuples of this `Block` are alive. */
117 : 340 : void mask(uint64_t new_mask) { mask_ = new_mask; }
118 : :
119 : : private:
120 : : /** Returns a bit vector with left-most `capacity()` many bits set to `1` and the others set to `0`. */
121 : 42 : static constexpr uint64_t AllOnes() { return -1UL >> (8 * sizeof(mask_) - capacity()); }
122 : :
123 : : public:
124 : : /** Returns the tuple at index `index`. The tuple must be *alive*! */
125 : 17400 : Tuple & operator[](std::size_t index) {
126 : 17400 : M_insist(index < capacity(), "index out of bounds");
127 : 17400 : M_insist(alive(index), "cannot access a dead tuple directly");
128 : 17400 : return data_[index];
129 : : }
130 : : /** Returns the tuple at index `index`. The tuple must be *alive*! */
131 : : const Tuple & operator[](std::size_t index) const { return const_cast<Block*>(this)->operator[](index); }
132 : :
133 : : /** Make all tuples in this `Block` *alive*. */
134 : 42 : void fill() { mask_ = AllOnes(); M_insist(size() == capacity()); }
135 : :
136 : : /** Erase the tuple at the given `index` from this `Block`. */
137 : 0 : void erase(std::size_t index) {
138 : 0 : M_insist(index < capacity(), "index out of bounds");
139 : 0 : setbit(&mask_, false, index);
140 : 0 : }
141 : : /** Erase the tuple identified by `it` from this `Block`. */
142 : 0 : void erase(iterator it) { erase(it.index()); }
143 : : /** Erase the tuple identified by `it` from this `Block`. */
144 : : void erase(const_iterator it) { erase(it.index()); }
145 : :
146 : : /** Renders all tuples *dead* and removes their attributes.. */
147 : 220 : void clear() {
148 : 220 : mask_ = 0;
149 [ + + ]: 14300 : for (auto &t : data_)
150 : 14080 : t.clear();
151 : 220 : }
152 : :
153 : : M_LCOV_EXCL_START
154 : : /** Print a textual representation of this `Block` to `out`. */
155 : : friend std::ostream & operator<<(std::ostream &out, const Block<N> &block) {
156 : : out << "Block<" << block.capacity() << "> with " << block.size() << " elements:\n";
157 : : for (std::size_t i = 0; i != block.capacity(); ++i) {
158 : : out << " " << i << ": ";
159 : : if (block.alive(i))
160 : : out << block[i];
161 : : else
162 : : out << "[dead]";
163 : : out << '\n';
164 : : }
165 : : return out;
166 : : }
167 : :
168 : : void dump(std::ostream &out) const
169 : : {
170 : : out << *this;
171 : : out.flush();
172 : : }
173 : : void dump() const { dump(std::cerr); }
174 : : M_LCOV_EXCL_STOP
175 : : };
176 : :
177 : : struct Interpreter;
178 : :
179 : : /** Implements push-based evaluation of a pipeline in the plan. */
180 : : struct Pipeline : ConstOperatorVisitor
181 : : {
182 : : friend struct Interpreter;
183 : :
184 : : private:
185 : : Block<64> block_;
186 : :
187 : : public:
188 [ # # ]: 0 : Pipeline() { }
189 : :
190 : 162 : Pipeline(const Schema &schema)
191 [ + - + - ]: 162 : : block_(schema)
192 : 162 : {
193 [ - + ]: 162 : block_.mask(1UL); // create one empty tuple in the block
194 : 162 : }
195 : :
196 : : Pipeline(Tuple &&t)
197 : : {
198 : : block_.mask(1UL);
199 : : block_[0] = std::move(t);
200 : : }
201 : :
202 : 191 : void push(const Operator &pipeline_start) { (*this)(pipeline_start); }
203 : :
204 : 110 : void clear() { block_.clear(); }
205 : :
206 : 68 : const Schema & schema() const { return block_.schema(); }
207 : :
208 : : using ConstOperatorVisitor::operator();
209 : : #define DECLARE(CLASS) void operator()(Const<CLASS> &op) override;
210 : : M_OPERATOR_LIST(DECLARE)
211 : : #undef DECLARE
212 : : };
213 : :
214 : : /** Evaluates SQL operator trees on the database. */
215 : : struct Interpreter : Backend, ConstOperatorVisitor
216 : : {
217 : : public:
218 [ + - ]: 7 : Interpreter() = default;
219 : :
220 : 81 : void register_operators(PhysicalOptimizer &phys_opt) const override { register_interpreter_operators(phys_opt); }
221 : :
222 : 81 : void execute(const MatchBase &plan) const override {
223 : 81 : (*const_cast<Interpreter*>(this))(plan.get_matched_root()); // use former visitor pattern on logical operators
224 : 81 : }
225 : :
226 : : using ConstOperatorVisitor::operator();
227 : : #define DECLARE(CLASS) void operator()(Const<CLASS> &op) override;
228 : : M_OPERATOR_LIST(DECLARE)
229 : : #undef DECLARE
230 : :
231 : 3277 : static Value eval(const ast::Constant &c)
232 : : {
233 : 3277 : errno = 0;
234 [ + + - + : 3277 : switch (c.tok.type) {
+ + + + +
- - - ]
235 : 0 : default: M_unreachable("illegal token");
236 : :
237 : : /* Null */
238 : : case TK_Null:
239 : 0 : M_unreachable("NULL cannot be evaluated to a Value");
240 : :
241 : : /* Integer */
242 : : case TK_OCT_INT:
243 : 46 : return int64_t(strtoll(*c.tok.text, nullptr, 8));
244 : :
245 : : case TK_DEC_INT:
246 : 2967 : return int64_t(strtoll(*c.tok.text, nullptr, 10));
247 : :
248 : : case TK_HEX_INT:
249 : 0 : return int64_t(strtoll(*c.tok.text, nullptr, 16));
250 : :
251 : : /* Float */
252 : : case TK_DEC_FLOAT:
253 : 59 : return strtod(*c.tok.text, nullptr);
254 : :
255 : : case TK_HEX_FLOAT:
256 : 0 : M_unreachable("not implemented");
257 : :
258 : : /* String */
259 : : case TK_STRING_LITERAL: {
260 [ + - ]: 50 : std::string str(*c.tok.text);
261 [ + - ]: 50 : auto substr = interpret(str);
262 [ + - + - : 50 : return Catalog::Get().pool(substr.c_str()); // return internalized string by reference
- + ]
263 : 50 : }
264 : :
265 : : /* Date */
266 : : case TK_DATE: {
267 : : int year, month, day;
268 [ + - ]: 7 : if (3 != sscanf(*c.tok.text, "d'%d-%d-%d'", &year, &month, &day))
269 : 0 : M_unreachable("invalid date");
270 : 7 : return int32_t(unsigned(year) << 9 | month << 5 | day);
271 : : }
272 : :
273 : : /* Datetime */
274 : : case TK_DATE_TIME: {
275 : : /* Extract date time from string. */
276 [ + - ]: 6 : std::string str_datetime(*c.tok.text);
277 [ + - + - ]: 6 : std::istringstream ss(str_datetime.substr(2, str_datetime.length() - 3));
278 : :
279 : : /* Parse date time. */
280 : : std::tm tm;
281 [ + - + - ]: 6 : ss >> get_tm(tm);
282 [ + - + - ]: 6 : M_insist(not ss.fail(), "failed to parse date time");
283 : :
284 : : #if defined(__APPLE__)
285 : : /* Adapt tm_year such that it is non-negative (i.e. >= 1900) since timegm() cannot handle these cases. */
286 : : constexpr long SECONDS_PER_400_YEAR_CYCLE = 12622780800L;
287 : : int cycles = tm.tm_year < 0 ? -tm.tm_year / 400 + 1 : 0;
288 : : tm.tm_year += cycles * 400;
289 : : M_insist(tm.tm_year >= 0);
290 : : #endif
291 : :
292 : : /* Convert date time from std::tm to time_t (seconds since epoch). */
293 : 6 : const time_t time = timegm(&tm);
294 [ + - ]: 6 : M_insist(time != -1, "datetime out of bounds");
295 : :
296 : : #if defined(__APPLE__)
297 : : return int64_t(time - cycles * SECONDS_PER_400_YEAR_CYCLE);
298 : : #else
299 [ + - ]: 6 : return int64_t(time);
300 : : #endif
301 : 6 : }
302 : :
303 : : /* Boolean */
304 : : case TK_True:
305 : 74 : return true;
306 : :
307 : : case TK_False:
308 : 68 : return false;
309 : : }
310 : : M_insist(errno == 0, "constant could not be parsed");
311 : 3277 : }
312 : :
313 : : /** Compile a `StackMachine` to load a tuple of `Schema` `tuple_schema` using a given memory address and a given
314 : : * `DataLayout`.
315 : : *
316 : : * @param tuple_schema the `Schema` of the tuple to load, specifying the `Schema::Identifier`s to load
317 : : * @param address the memory address of the `Store` we are loading from
318 : : * @param layout the `DataLayout` of the `Table` we are loading from
319 : : * @param layout_schema the `Schema` of `layout`, specifying the `Schema::Identifier`s present in `layout`
320 : : * @param row_id the ID of the *first* row to load
321 : : * @param tuple_id the ID of the tuple used for loading
322 : : */
323 : : static StackMachine compile_load(const Schema &tuple_schema, void *address, const storage::DataLayout &layout,
324 : : const Schema &layout_schema, std::size_t row_id = 0, std::size_t tuple_id = 0);
325 : :
326 : : /** Compile a `StackMachine` to store a tuple of `Schema` `tuple_schema` using a given memory address and a given
327 : : * `DataLayout`.
328 : : *
329 : : * @param tuple_schema the `Schema` of the tuple to store, specifying the `Schema::Identifier`s to store
330 : : * @param address the memory address of the `Store` we are storing to
331 : : * @param layout the `DataLayout` of the `Table` we are storing to
332 : : * @param layout_schema the `Schema` of `layout`, specifying the `Schema::Identifier`s present in `layout`
333 : : * @param row_id the ID of the *first* row to store
334 : : * @param tuple_id the ID of the tuple used for storing
335 : : */
336 : : static StackMachine compile_store(const Schema &tuple_schema, void *address, const storage::DataLayout &layout,
337 : : const Schema &layout_schema, std::size_t row_id = 0, std::size_t tuple_id = 0);
338 : : };
339 : :
340 : : }
|
