finish adding json output
[benchmarks.git] / src / json.h
1 #pragma once
2
3 #include <cassert>
4 #include <charconv>
5 #include <cmath>
6 #include <cstddef>
7 #include <cstdint>
8 #include <cstdio>
9 #include <cstdlib>
10 #include <exception>
11 #include <functional>
12 #include <initializer_list>
13 #include <ios>
14 #include <iterator>
15 #include <memory>
16 #include <optional>
17 #include <ostream>
18 #include <string>
19 #include <string_view>
20 #include <system_error>
21 #include <type_traits>
22 #include <unordered_map>
23 #include <variant>
24 #include <vector>
25
26 enum class ResolveResult : bool
27 {
28 Finished = false,
29 MoreToResolve = true,
30 };
31
32 template <typename T> class LazyVec final
33 {
34 private:
35 struct Internals
36 {
37 std::vector<T> resolved_values;
38 explicit Internals(std::vector<T> &&resolved_values)
39 : resolved_values(std::move(resolved_values))
40 {
41 }
42 explicit Internals(std::initializer_list<T> resolved_values = {})
43 : resolved_values(resolved_values)
44 {
45 }
46 virtual ~Internals() = default;
47 virtual ResolveResult resolve_more()
48 {
49 return ResolveResult::Finished;
50 }
51 };
52 template <
53 typename Iterator, typename Sentinel,
54 typename = std::enable_if_t<
55 std::is_base_of_v<
56 std::input_iterator_tag,
57 typename std::iterator_traits<Iterator>::iterator_category> &&
58 std::is_same_v<
59 const typename std::iterator_traits<Iterator>::value_type,
60 const T>>>
61 struct LazyInternalsIter final : public Internals
62 {
63 struct State final
64 {
65 Iterator cur;
66 Sentinel end;
67 State(Iterator &&cur, Sentinel &&end) noexcept
68 : cur(std::move(cur)), end(std::move(end))
69 {
70 }
71 };
72 std::optional<State> state;
73 LazyInternalsIter(Iterator &&cur, Sentinel &&end) noexcept
74 : state(std::in_place, std::move(cur), std::move(end))
75 {
76 if (state->cur == state->end)
77 {
78 state = std::nullopt;
79 }
80 }
81 LazyInternalsIter(const LazyInternalsIter &) = delete;
82 LazyInternalsIter &operator=(const LazyInternalsIter &) = delete;
83 virtual ResolveResult resolve_more() override
84 {
85 if (!state)
86 {
87 return ResolveResult::Finished;
88 }
89 this->resolved_values.emplace_back(*state->cur++);
90 if (state->cur == state->end)
91 {
92 state = std::nullopt;
93 return ResolveResult::Finished;
94 }
95 return ResolveResult::MoreToResolve;
96 }
97 };
98 template <
99 typename Container,
100 typename Iterator = decltype(std::begin(std::declval<Container>())),
101 typename Sentinel = decltype(std::end(std::declval<Container>())),
102 typename = decltype(LazyInternalsIter<Iterator, Sentinel>::cur)>
103 struct LazyInternalsContainer final : public Internals
104 {
105 struct State final
106 {
107 Container container;
108 Iterator cur; // must come after container
109 Sentinel end; // must come after container
110 explicit State(Container &&container) noexcept
111 : container(std::move(container)),
112 cur(std::begin(this->container)),
113 end(std::begin(this->container))
114 {
115 }
116 State(const State &) = delete;
117 State &operator=(const State &) = delete;
118 };
119 std::optional<State> state;
120 explicit LazyInternalsContainer(Container &&container) noexcept
121 : state(std::in_place, std::move(container))
122 {
123 if (state->cur == state->end)
124 {
125 state = std::nullopt;
126 }
127 }
128 virtual ResolveResult resolve_more() override
129 {
130 if (!state)
131 {
132 return ResolveResult::Finished;
133 }
134 this->resolved_values.emplace_back(*state->cur++);
135 if (state->cur == state->end)
136 {
137 state = std::nullopt;
138 return ResolveResult::Finished;
139 }
140 return ResolveResult::MoreToResolve;
141 }
142 };
143 template <typename Fn,
144 typename = std::enable_if_t<std::is_convertible_v<
145 decltype(std::declval<Fn &>()()), std::optional<T>>>>
146 struct LazyInternalsFn final : public Internals
147 {
148 std::optional<Fn> fn;
149 explicit LazyInternalsFn(Fn &&fn) noexcept
150 : fn(std::in_place, std::move(fn))
151 {
152 }
153 virtual ResolveResult resolve_more() override
154 {
155 if (!fn)
156 {
157 return ResolveResult::Finished;
158 }
159 if (std::optional<T> value = (*fn)())
160 {
161 this->resolved_values.emplace_back(std::move(*value));
162 return ResolveResult::MoreToResolve;
163 }
164 fn = std::nullopt;
165 return ResolveResult::Finished;
166 }
167 };
168 std::shared_ptr<Internals> internals;
169
170 public:
171 LazyVec() noexcept : internals(std::make_shared<Internals>())
172 {
173 }
174 LazyVec(std::vector<T> values) noexcept
175 : internals(std::make_shared<Internals>(std::move(values)))
176 {
177 }
178 LazyVec(std::initializer_list<T> values) noexcept
179 : internals(std::make_shared<Internals>(values))
180 {
181 }
182 template <typename Iterator, typename Sentinel,
183 typename = decltype(LazyInternalsIter<Iterator, Sentinel>::cur)>
184 LazyVec(Iterator begin, Sentinel end) noexcept
185 : internals(std::make_shared<LazyInternalsIter<Iterator, Sentinel>>(
186 std::move(begin), std::move(end)))
187 {
188 }
189 template <typename Container, typename = decltype(LazyInternalsContainer<
190 Container>::container)>
191 LazyVec(Container container) noexcept
192 : internals(std::make_shared<LazyInternalsContainer<Container>>(
193 std::move(container)))
194 {
195 }
196 template <typename Fn, typename = void,
197 typename = decltype(LazyInternalsFn<Fn>::fn)>
198 LazyVec(Fn fn) noexcept
199 : internals(std::make_shared<LazyInternalsFn<Fn>>(std::move(fn)))
200 {
201 }
202
203 private:
204 static bool resolve_at(const std::shared_ptr<Internals> &internals,
205 std::size_t index) noexcept
206 {
207 while (index >= internals->resolved_values.size())
208 {
209 switch (internals->resolve_more())
210 {
211 case ResolveResult::Finished:
212 goto end;
213 case ResolveResult::MoreToResolve:
214 continue;
215 }
216 }
217 end:
218 return index < internals->resolved_values.size();
219 }
220
221 public:
222 bool resolve_at(std::size_t index) noexcept
223 {
224 return resolve_at(internals, index);
225 }
226 const T &at(std::size_t index) noexcept
227 {
228 if (!resolve_at(index))
229 {
230 assert(!"index out of bounds");
231 std::terminate();
232 }
233 return internals->resolved_values[index];
234 }
235 const T &operator[](std::size_t index) noexcept
236 {
237 return at(index);
238 }
239 std::size_t size_lower_bound() noexcept
240 {
241 return internals->resolved_values.size();
242 }
243 ResolveResult resolve_more()
244 {
245 return internals->resolve_more();
246 }
247 const std::vector<T> &resolve()
248 {
249 while (true)
250 {
251 switch (resolve_more())
252 {
253 case ResolveResult::Finished:
254 return internals->resolved_values;
255 case ResolveResult::MoreToResolve:
256 continue;
257 }
258 }
259 }
260 class const_iterator final
261 {
262 friend class LazyVec;
263
264 private:
265 std::shared_ptr<Internals> internals;
266 std::size_t index = 0;
267 bool resolve() const noexcept
268 {
269 assert(internals);
270 if (!internals)
271 {
272 std::terminate();
273 }
274 return resolve_at(internals, index);
275 }
276 explicit const_iterator(
277 const std::shared_ptr<Internals> &internals) noexcept
278 : internals(internals)
279 {
280 }
281
282 public:
283 using difference_type = std::ptrdiff_t;
284 using value_type = T;
285 using pointer = const T *;
286 using reference = const T &;
287 using iterator_category = std::forward_iterator_tag;
288
289 const_iterator() noexcept = default;
290 const_iterator &operator++()
291 {
292 assert(internals);
293 ++index;
294 return *this;
295 }
296 const_iterator operator++(int)
297 {
298 auto retval = *this;
299 operator++();
300 return retval;
301 }
302 pointer operator->() const noexcept
303 {
304 if (at_end())
305 {
306 assert(!"tried to dereference an end() iterator");
307 std::terminate();
308 }
309 return std::addressof(internals->resolved_values[index]);
310 }
311 reference operator*() const noexcept
312 {
313 return *operator->();
314 }
315 bool at_end() const noexcept
316 {
317 return !resolve();
318 }
319 bool operator==(const const_iterator &rhs) const noexcept
320 {
321 if (rhs.internals)
322 {
323 if (internals)
324 {
325 assert(internals == rhs.internals);
326 return index == rhs.index;
327 }
328 return rhs.at_end();
329 }
330 if (internals)
331 {
332 return at_end();
333 }
334 return true;
335 }
336 bool operator!=(const const_iterator &rhs) const noexcept
337 {
338 return !operator==(rhs);
339 }
340 };
341 const_iterator begin() const noexcept
342 {
343 return const_iterator(internals);
344 }
345 const_iterator cbegin() const noexcept
346 {
347 return const_iterator(internals);
348 }
349 const_iterator end() const noexcept
350 {
351 return const_iterator();
352 }
353 const_iterator cend() const noexcept
354 {
355 return const_iterator();
356 }
357 template <typename R, typename Fn> LazyVec<R> filter_map(Fn &&fn) noexcept
358 {
359 struct FilterMapper final
360 {
361 const_iterator iter;
362 Fn fn;
363 std::optional<R> operator()() noexcept
364 {
365 while (iter != const_iterator())
366 {
367 if (std::optional<R> retval = fn(*iter++))
368 {
369 return retval;
370 }
371 }
372 return std::nullopt;
373 }
374 };
375 return LazyVec<R>(FilterMapper{.iter = begin(), .fn = std::move(fn)});
376 }
377 template <typename R, typename Fn> LazyVec<R> map(Fn fn) noexcept
378 {
379 return filter_map<R>(
380 [fn](const T &value) -> std::optional<R> { return fn(value); });
381 }
382 template <typename Fn> LazyVec filter(Fn fn) noexcept
383 {
384 return filter_map<T>([fn](const T &value) -> std::optional<T> {
385 if (fn(value))
386 return value;
387 return std::nullopt;
388 });
389 }
390 };
391
392 struct JsonValue;
393
394 struct JsonValue final
395 {
396 using String = std::string;
397 using Number = double;
398 using Object = LazyVec<std::pair<String, JsonValue>>;
399 using Array = LazyVec<JsonValue>;
400 using Bool = bool;
401 using Null = std::nullptr_t;
402 std::variant<String, Number, Object, Array, Bool, Null> value;
403 constexpr JsonValue() noexcept : value(nullptr)
404 {
405 }
406 JsonValue(String value) noexcept : value(std::move(value))
407 {
408 }
409 JsonValue(const char *value) noexcept : value(std::string(value))
410 {
411 }
412 JsonValue(std::string_view value) noexcept : value(std::string(value))
413 {
414 }
415 constexpr JsonValue(Number value) noexcept : value(value)
416 {
417 }
418 JsonValue(Object value) noexcept : value(std::move(value))
419 {
420 }
421 JsonValue(Array value) noexcept : value(std::move(value))
422 {
423 }
424 constexpr JsonValue(Bool value) noexcept : value(value)
425 {
426 }
427 constexpr JsonValue(Null) noexcept : value(nullptr)
428 {
429 }
430 constexpr JsonValue(char) noexcept = delete;
431 constexpr JsonValue(char16_t) noexcept = delete;
432 constexpr JsonValue(char32_t) noexcept = delete;
433 #define JSON_VALUE_NUM(T) \
434 constexpr JsonValue(T value) noexcept \
435 : JsonValue(static_cast<double>(value)) \
436 { \
437 }
438 JSON_VALUE_NUM(float)
439 JSON_VALUE_NUM(long double)
440 JSON_VALUE_NUM(unsigned char)
441 JSON_VALUE_NUM(signed char)
442 JSON_VALUE_NUM(unsigned short)
443 JSON_VALUE_NUM(short)
444 JSON_VALUE_NUM(unsigned int)
445 JSON_VALUE_NUM(int)
446 JSON_VALUE_NUM(unsigned long)
447 JSON_VALUE_NUM(long)
448 JSON_VALUE_NUM(unsigned long long)
449 JSON_VALUE_NUM(long long)
450 #undef JSON_VALUE_NUM
451 template <typename T, typename = decltype(JsonValue(std::declval<T &&>()))>
452 constexpr JsonValue(std::optional<T> value) noexcept : value(nullptr)
453 {
454 if (value)
455 {
456 *this = JsonValue(std::move(*value));
457 }
458 }
459 template <typename T,
460 typename = decltype(JsonValue(std::declval<const T &>()))>
461 JsonValue(LazyVec<T> value) noexcept
462 : value(value.template map<JsonValue>(
463 [](const T &value) { return JsonValue(value); }))
464 {
465 }
466 template <typename T,
467 typename = decltype(JsonValue(std::declval<const T &>()))>
468 JsonValue(std::vector<T> value) noexcept
469 : JsonValue(LazyVec<T>(std::move(value)))
470 {
471 }
472 /// decode a JsonString from WTF-8 to the encoding logically used in JSON:
473 /// WTF-16 aka. potentially ill-formed UTF-16
474 ///
475 /// https://simonsapin.github.io/wtf-8/
476 class JsonStringDecoder final
477 {
478 private:
479 std::string_view remaining;
480 bool last_was_lead_surrogate = false;
481 std::optional<std::uint16_t> trail_surrogate;
482
483 public:
484 constexpr JsonStringDecoder() noexcept : JsonStringDecoder("")
485 {
486 }
487 constexpr explicit JsonStringDecoder(
488 std::string_view json_string) noexcept
489 : remaining(json_string)
490 {
491 }
492
493 private:
494 [[noreturn]] void throw_wtf8_err()
495 {
496 *this = JsonStringDecoder();
497 throw std::ios_base::failure("Invalid WTF-8");
498 }
499
500 public:
501 constexpr std::optional<std::uint16_t> next()
502 {
503 if (trail_surrogate)
504 {
505 auto retval = *trail_surrogate;
506 trail_surrogate = std::nullopt;
507 return retval;
508 }
509 if (remaining.empty())
510 {
511 return std::nullopt;
512 }
513 std::uint32_t code_point = 0;
514 struct min_max final
515 {
516 std::uint8_t min = 0x80;
517 std::uint8_t max = 0xBF;
518 };
519 auto get = [&]() -> std::uint8_t {
520 if (remaining.empty())
521 {
522 throw_wtf8_err();
523 }
524 std::uint8_t retval = remaining[0];
525 remaining.remove_prefix(1);
526 return retval;
527 };
528 auto cont = [&](min_max min_max = {}) {
529 std::uint8_t v = get();
530 if (v < min_max.min || v > min_max.max)
531 {
532 throw_wtf8_err();
533 }
534 code_point <<= 6;
535 code_point |= v & 0x3F;
536 };
537 std::uint8_t initial = get();
538 if (initial < 0x80)
539 {
540 code_point = initial;
541 }
542 else if (initial < 0xC2)
543 {
544 throw_wtf8_err();
545 }
546 else if (initial < 0xE0)
547 {
548 code_point = initial & 0x1F;
549 cont();
550 }
551 else if (initial == 0xE0)
552 {
553 code_point = initial & 0xF;
554 cont({.min = 0xA0});
555 cont();
556 }
557 else if (initial < 0xF0)
558 {
559 code_point = initial & 0xF;
560 cont();
561 cont();
562 }
563 else if (initial == 0xF0)
564 {
565 code_point = initial & 0x7;
566 cont({.min = 0x90});
567 cont();
568 cont();
569 }
570 else if (initial < 0xF4)
571 {
572 code_point = initial & 0x7;
573 cont();
574 cont();
575 cont();
576 }
577 else if (initial == 0xF4)
578 {
579 code_point = initial & 0x7;
580 cont({.max = 0x8F});
581 cont();
582 cont();
583 }
584 else
585 {
586 throw_wtf8_err();
587 }
588 if (last_was_lead_surrogate && code_point >= 0xDC00 &&
589 code_point <= 0xDFFF)
590 {
591 // got lead surrogate followed by trail surrogate --
592 // invalid in WTF-8
593 throw_wtf8_err();
594 }
595 last_was_lead_surrogate =
596 (code_point >= 0xD800 && code_point <= 0xDBFF);
597 bool is_supplementary_code_point = code_point >= 0x10000;
598 if (is_supplementary_code_point)
599 {
600 auto value = code_point - 0x10000;
601 std::uint16_t retval = (value >> 10) + 0xD800;
602 trail_surrogate = (value & 0x3FF) + 0xDC00;
603 return retval;
604 }
605 else
606 {
607 return code_point;
608 }
609 }
610 };
611
612 private:
613 template <typename WriteStringView> struct Visitor final
614 {
615 WriteStringView &write_fn;
616 bool pretty;
617 std::size_t indent = 0;
618 void write(std::string_view str)
619 {
620 write_fn(str);
621 }
622 void write(char ch)
623 {
624 write_fn(std::string_view(&ch, 1));
625 }
626 void write_indent()
627 {
628 for (std::size_t i = 0; i < indent; i++)
629 {
630 write(" ");
631 }
632 }
633 void operator()(const String &value)
634 {
635 write('\"');
636 JsonStringDecoder decoder(value);
637 while (auto value_opt = decoder.next())
638 {
639 std::uint16_t value = *value_opt;
640 switch (value)
641 {
642 case '\"':
643 case '\\':
644 write('\\');
645 write(static_cast<char>(value));
646 break;
647 case '\b':
648 write("\\b");
649 break;
650 case '\f':
651 write("\\f");
652 break;
653 case '\n':
654 write("\\n");
655 break;
656 case '\r':
657 write("\\r");
658 break;
659 case '\t':
660 write("\\t");
661 break;
662 default:
663 if (value >= 0x20 && value <= 0x7E)
664 {
665 write(static_cast<char>(value));
666 }
667 else
668 {
669 static constexpr char hex_digits[] =
670 "0123456789ABCDEF";
671 write("\\u");
672 for (int i = 0; i < 4; i++)
673 {
674 write(hex_digits[value >> 12]);
675 value <<= 4;
676 }
677 }
678 break;
679 }
680 }
681 write('"');
682 }
683 void operator()(Number value)
684 {
685 if (std::isnan(value))
686 {
687 write("NaN");
688 return;
689 }
690 if (std::signbit(value))
691 {
692 write('-');
693 value = -value;
694 }
695 if (std::isinf(value))
696 {
697 write("Infinity");
698 return;
699 }
700 if (value == 0)
701 {
702 write("0");
703 return;
704 }
705 using Buf = std::array<char, 32>;
706 auto try_format = [&](Buf &buf, bool e_format, int prec) -> bool {
707 int result;
708 if (e_format)
709 {
710 result = std::snprintf(&buf[0], buf.size(), "%1.*e", prec,
711 value);
712 }
713 else
714 {
715 result = std::snprintf(&buf[0], buf.size(), "%1.*f", prec,
716 value);
717 }
718 if (result <= 0)
719 return false;
720 double parsed_value = std::strtod(&buf[0], nullptr);
721 if (parsed_value != value)
722 {
723 // not precise enough
724 return false;
725 }
726 return true;
727 };
728 Buf final_buf = {};
729 std::optional<std::string_view> final;
730 std::size_t end_prec = final_buf.size();
731 for (std::size_t prec = 0;
732 prec < final_buf.size() && prec < end_prec; prec++)
733 {
734 Buf buf;
735 if (try_format(buf, true, prec))
736 {
737 std::string_view str(&buf[0]);
738 if (!final || str.size() < final->size())
739 {
740 final_buf = buf;
741 final = std::string_view(&final_buf[0], str.size());
742 end_prec = prec + 3;
743 }
744 }
745 if (try_format(buf, false, prec))
746 {
747 std::string_view str(&buf[0]);
748 if (!final || str.size() < final->size())
749 {
750 final_buf = buf;
751 final = std::string_view(&final_buf[0], str.size());
752 end_prec = prec + 3;
753 }
754 }
755 }
756 if (final_buf[0] == '.')
757 {
758 write('0');
759 }
760 write(*final);
761 }
762 void operator()(Bool value)
763 {
764 write(value ? "true" : "false");
765 }
766 void operator()(Null)
767 {
768 write("null");
769 }
770 template <typename T, typename Fn>
771 void write_container_inner(const LazyVec<T> &value, Fn fn)
772 {
773 indent++;
774 std::string_view sep{};
775 bool any = false;
776 for (auto &v : value)
777 {
778 any = true;
779 write(sep);
780 if (pretty)
781 {
782 write('\n');
783 write_indent();
784 }
785 sep = ",";
786 fn(v);
787 }
788 indent--;
789 if (pretty && any)
790 {
791 write('\n');
792 write_indent();
793 }
794 }
795 void operator()(const Array &value)
796 {
797 write('[');
798 write_container_inner(value, [&](const JsonValue &value) {
799 std::visit(*this, value.value);
800 });
801 write(']');
802 }
803 void operator()(const Object &value)
804 {
805 write('{');
806 write_container_inner(
807 value, [&](const std::pair<String, JsonValue> &value) {
808 operator()(value.first);
809 write(':');
810 if (pretty)
811 {
812 write(' ');
813 }
814 std::visit(*this, value.second.value);
815 });
816 write('}');
817 }
818 };
819
820 public:
821 template <typename WriteStringView>
822 void write(WriteStringView &&write_fn, bool pretty = false) const
823 {
824 std::visit(
825 Visitor<WriteStringView>{
826 .write_fn = write_fn,
827 .pretty = pretty,
828 },
829 value);
830 }
831 struct PrettyJsonValue;
832 PrettyJsonValue pretty(bool pretty = true) const noexcept;
833 friend std::ostream &operator<<(std::ostream &os, const JsonValue &self)
834 {
835 self.write([&](std::string_view str) { os << str; });
836 return os;
837 }
838 };
839
840 struct JsonValue::PrettyJsonValue final
841 {
842 JsonValue value;
843 bool pretty;
844 friend std::ostream &operator<<(std::ostream &os,
845 const PrettyJsonValue &self)
846 {
847 self.value.write([&](std::string_view str) { os << str; },
848 self.pretty);
849 return os;
850 }
851 };
852
853 inline auto JsonValue::pretty(bool pretty) const noexcept -> PrettyJsonValue
854 {
855 return {.value = *this, .pretty = pretty};
856 }