9 #include <unordered_map> 39 class RuntimeError :
public TREE_RUNTIME_ERROR {
41 explicit RuntimeError(
const std::string &msg) : TREE_RUNTIME_ERROR(msg) {}
47 class NotWellFormed :
public RuntimeError {
49 explicit NotWellFormed(
const std::string &msg) : RuntimeError(msg) {}
56 class OutOfRange :
public TREE_RANGE_ERROR {
58 explicit OutOfRange(
const std::string &msg) : TREE_RANGE_ERROR(msg) {}
73 TREE_MAP(
const void*,
size_t) map;
79 size_t add_raw(
const void *ptr,
const char *name);
85 size_t get_raw(
const void *ptr,
const char *name)
const;
92 static const size_t INVALID = (size_t)-1;
99 bool enable_exceptions =
true;
107 size_t add(
const Maybe<T> &ob);
116 size_t add_ref(
const T &ob);
124 size_t get(
const Maybe<T> &ob)
const;
132 size_t get(
const OptLink<T> &ob)
const;
140 size_t get_ref(
const T &ob)
const;
149 class IdentifierMap {
155 TREE_MAP(
size_t, std::shared_ptr<void>) nodes;
160 using Link = std::pair<LinkBase&, size_t>;
161 TREE_VECTOR(
Link) links;
168 void register_node(
size_t identifier,
const std::shared_ptr<void> &ptr);
173 void register_link(LinkBase &link,
size_t identifier);
178 void restore_links()
const;
187 virtual ~Completable() =
default;
195 virtual void find_reachable(PointerMap &map)
const;
207 virtual void check_complete(
const PointerMap &map)
const;
219 virtual void check_well_formed() const final;
230 virtual
bool is_well_formed() const final;
237 class Base : public annotatable::Annotatable, public Completable {
244 class Maybe :
public Completable {
250 std::shared_ptr<T> val;
263 explicit Maybe(
const std::shared_ptr<S> &value) : val(
std::static_pointer_cast<T>(value)) {}
269 explicit Maybe(std::shared_ptr<S> &&value) : val(
std::static_pointer_cast<T>(
std::move(value))) {}
276 Maybe(
const Maybe<S> &value) : val(
std::static_pointer_cast<T>(value.get_ptr())) {}
283 Maybe(Maybe<S> &&value) : val(
std::static_pointer_cast<T>(
std::move(value.get_ptr()))) {}
288 template<
typename S = T,
class... Args>
289 void emplace(Args&&... args) {
290 val = std::static_pointer_cast<T>(std::make_shared<S>(std::forward<Args>(args)...));
296 template<
typename S = T,
class... Args>
297 static One<T> make(Args&&... args);
303 void set(
const std::shared_ptr<S> &value) {
304 val = std::static_pointer_cast<T>(value);
311 Maybe &operator=(
const std::shared_ptr<S> &value) {
320 void set(std::shared_ptr<S> &&value) {
321 val = std::static_pointer_cast<T>(std::move(value));
328 Maybe &operator=(std::shared_ptr<S> &&value) {
329 set<S>(std::move(value));
337 void set(
const Maybe<S> &value) {
338 val = std::static_pointer_cast<T>(value.get_ptr());
345 Maybe &operator=(
const Maybe<S> &value) {
346 set<S>(std::move(value));
354 void set(Maybe<S> &&value) {
355 val = std::static_pointer_cast<T>(std::move(value.get_ptr()));
362 Maybe &operator=(Maybe<S> &&value) {
363 set<S>(std::move(value));
375 void set_raw(S *ob) {
376 val = std::shared_ptr<T>(
static_cast<T*
>(ob));
389 virtual bool empty()
const {
390 return val ==
nullptr;
396 size_t size()
const {
408 std::string(
"dereferencing empty Maybe/One object of type ") +
419 T &operator*()
const {
427 T *operator->()
const {
434 const std::shared_ptr<T> &get_ptr()
const {
441 std::shared_ptr<T> &get_ptr() {
451 Maybe<S> as()
const {
452 return Maybe<S>(std::dynamic_pointer_cast<S>(val));
458 Maybe<const T> as_const()
const {
459 return Maybe<const T>(std::const_pointer_cast<
const T>(val));
466 void visit(V &visitor) {
475 bool equals(
const Maybe &rhs)
const {
476 if (val && rhs.get_ptr()) {
477 if (val == rhs.val) {
480 return val->equals(*rhs);
483 return val == rhs.get_ptr();
490 bool operator==(
const Maybe &rhs)
const {
491 return val == rhs.get_ptr();
497 bool operator!=(
const Maybe &rhs)
const {
498 return val != rhs.get_ptr();
504 bool operator>(
const Maybe &rhs)
const {
505 return val > rhs.val;
511 bool operator>=(
const Maybe &rhs)
const {
512 return val >= rhs.val;
518 bool operator<(
const Maybe &rhs)
const {
519 return val < rhs.val;
525 bool operator<=(
const Maybe &rhs)
const {
526 return val <= rhs.val;
535 void find_reachable(PointerMap &map)
const override {
538 val->find_reachable(map);
552 void check_complete(
const PointerMap &map)
const override {
554 val->check_complete(map);
561 One<typename std::remove_const<T>::type> copy()
const;
568 One<typename std::remove_const<T>::type> clone()
const;
575 virtual std::string serdes_edge_type()
const {
584 void deserialize(
const cbor::MapReader &map, IdentifierMap &ids) {
588 if (map.at(
"@T").as_string() != serdes_edge_type()) {
589 throw RuntimeError(
"Schema validation failed: unexpected edge type");
591 auto type = map.at(
"@t");
592 if (type.is_null()) {
595 val = T::deserialize(map, ids);
596 ids.register_node(map.at(
"@i").as_int(), std::static_pointer_cast<
void>(val));
607 void serialize(cbor::MapWriter &map,
const PointerMap &ids)
const {
608 map.append_string(
"@T", serdes_edge_type());
610 map.append_int(
"@i", ids.get(*
this));
611 val->serialize(map, ids);
613 map.append_null(
"@t");
621 Maybe(
const cbor::MapReader &map, IdentifierMap &ids) : val() {
622 deserialize(map, ids);
643 explicit One(
const std::shared_ptr<S> &value) :
Maybe<T>(value) {}
649 explicit One(std::shared_ptr<S> &&value) :
Maybe<T>(
std::move(value)) {}
655 One(
const Maybe<S> &value) :
Maybe<T>(value.get_ptr()) {}
661 One(Maybe<S> &&value) :
Maybe<T>(
std::move(value.get_ptr())) {}
673 void check_complete(
const PointerMap &map)
const override {
675 std::ostringstream ss{};
676 ss <<
"'One' edge of type " <<
typeid(T).name() <<
" is empty";
677 throw NotWellFormed(ss.str());
679 this->val->check_complete(map);
687 std::string serdes_edge_type()
const override {
697 One(
const cbor::MapReader &map, IdentifierMap &ids) :
Maybe<T>() {
698 this->deserialize(map, ids);
707 One<typename std::remove_const<T>::type> Maybe<T>::copy()
const {
719 One<typename std::remove_const<T>::type> Maybe<T>::clone()
const {
731 template<
typename S,
class... Args>
732 One<T> Maybe<T>::make(Args&&... args) {
733 return One<T>(std::static_pointer_cast<T>(std::make_shared<S>(std::forward<Args>(args)...)));
739 template <
class T,
typename... Args>
740 One<T> make(Args... args) {
741 return One<T>(std::make_shared<T>(args...));
748 class Any :
public Completable {
754 TREE_VECTOR(One<T>) vec;
758 using iterator =
typename TREE_VECTOR(One<T>)::iterator;
759 using Iterator = iterator;
760 using const_iterator =
typename TREE_VECTOR(One<T>)::const_iterator;
761 using ConstIterator = const_iterator;
762 using reverse_iterator =
typename TREE_VECTOR(One<T>)::reverse_iterator;
763 using ReverseIterator = reverse_iterator;
764 using const_reverse_iterator =
typename TREE_VECTOR(One<T>)::const_reverse_iterator;
765 using ConstReverseIterator = const_reverse_iterator;
775 Any(std::initializer_list<One<T>> inits) : vec(inits) {
782 void add(
const Maybe<S> &ob, signed_size_t pos=-1) {
786 if (pos < 0 || (
size_t)pos >= size()) {
787 this->vec.emplace_back(
788 std::static_pointer_cast<T>(ob.get_ptr()));
790 this->vec.emplace(this->vec.cbegin() + pos,
791 std::static_pointer_cast<T>(
799 template <
class S = T,
typename... Args>
800 Any &emplace(Args... args) {
801 this->vec.emplace_back(std::static_pointer_cast<T>(std::make_shared<S>(std::forward<Args>(args)...)));
813 void add_raw(S *ob, signed_size_t pos=-1) {
815 throw RuntimeError(
"add_raw called with nullptr!");
817 if (pos < 0 || (
size_t)pos >= size()) {
818 this->vec.emplace_back(std::shared_ptr<T>(static_cast<T*>(ob)));
820 this->vec.emplace(this->vec.cbegin() + pos, std::shared_ptr<T>(
static_cast<T*
>(ob)));
827 void extend(
const Any<T> &other) {
828 this->vec.insert(this->vec.end(), other.vec.begin(), other.vec.end());
835 void remove(signed_size_t pos=-1) {
839 if (pos < 0 || (
size_t)pos >= size()) {
842 this->vec.erase(this->vec.cbegin() + pos);
855 virtual bool empty()
const {
862 size_t size()
const {
870 const One<T> &at(
size_t index)
const {
871 return vec.at(index);
878 One<T> &at(
size_t index) {
879 return vec.at(index);
886 const One<T> &operator[] (
size_t index)
const {
894 One<T> &operator[] (
size_t index) {
902 Maybe<T> front()
const {
914 Maybe<T> back()
const {
932 ConstIterator begin()
const {
946 ConstIterator end()
const {
953 ReverseIterator rbegin() {
960 ConstReverseIterator rbegin()
const {
967 ReverseIterator rend() {
974 ConstReverseIterator rend()
const {
982 void visit(V &visitor) {
983 for (
auto &sptr : this->vec) {
985 sptr->visit(visitor);
993 bool equals(
const Any &rhs)
const {
994 if (vec.size() != rhs.vec.size()) {
997 for (
size_t i = 0; i < vec.size(); i++) {
998 if (!vec[i].equals(rhs.vec[i])) {
1008 bool operator==(
const Any &rhs)
const {
1009 return vec == rhs.vec;
1015 inline bool operator!=(
const Any &rhs)
const {
1016 return !(*
this == rhs);
1022 const TREE_VECTOR(One<T>) &get_vec()
const {
1029 TREE_VECTOR(One<T>) &get_vec() {
1039 void find_reachable(PointerMap &map)
const override {
1040 for (
auto &sptr : this->vec) {
1041 sptr.find_reachable(map);
1055 void check_complete(
const PointerMap &map)
const override {
1056 for (
auto &sptr : this->vec) {
1057 sptr.check_complete(map);
1064 Many<typename std::remove_const<T>::type> copy()
const;
1069 Many<typename std::remove_const<T>::type> clone()
const;
1076 virtual std::string serdes_edge_type()
const {
1085 void deserialize(
const cbor::MapReader &map, IdentifierMap &ids) {
1089 if (map.at(
"@T").as_string() != serdes_edge_type()) {
1090 throw RuntimeError(
"Schema validation failed: unexpected edge type");
1092 for (
const auto &it : map.at(
"@d").as_array()) {
1093 vec.emplace_back(it.as_map(), ids);
1104 void serialize(cbor::MapWriter &map,
const PointerMap &ids)
const {
1105 map.append_string(
"@T", serdes_edge_type());
1106 auto ar = map.append_array(
"@d");
1107 for (
auto &sptr : this->vec) {
1108 auto submap = ar.append_map();
1109 sptr.serialize(submap, ids);
1117 Any(
const cbor::MapReader &map, IdentifierMap &ids) : vec() {
1118 deserialize(map, ids);
1138 Many(std::initializer_list<One<T>> inits) :
Any<T>(inits) {
1151 void check_complete(
const PointerMap &map)
const override {
1152 if (this->empty()) {
1153 std::ostringstream ss{};
1154 ss <<
"'Many' edge of type " <<
typeid(T).name() <<
" is empty";
1155 throw NotWellFormed(ss.str());
1157 Any<T>::check_complete(map);
1165 std::string serdes_edge_type()
const override {
1175 Many(
const cbor::MapReader &map, IdentifierMap &ids) :
Any<T>() {
1176 this->deserialize(map, ids);
1185 Many<typename std::remove_const<T>::type> Any<T>::copy()
const {
1186 Many<typename std::remove_const<T>::type> c{};
1187 for (
auto &sptr : this->vec) {
1197 Many<typename std::remove_const<T>::type> Any<T>::clone()
const {
1198 Many<typename std::remove_const<T>::type> c{};
1199 for (
auto &sptr : this->vec) {
1200 c.add(sptr.clone());
1208 class LinkBase :
public Completable {
1210 friend class IdentifierMap;
1215 virtual void set_void_ptr(
const std::shared_ptr<void> &ptr) = 0;
1223 class OptLink :
public LinkBase {
1229 std::weak_ptr<T> val;
1242 OptLink(
const Maybe<S> &value) : val(
std::static_pointer_cast<T>(value.get_ptr())) {}
1248 OptLink(Maybe<S> &&value) : val(
std::static_pointer_cast<T>(
std::move(value.get_ptr()))) {}
1254 OptLink(
const OptLink<S> &value) : val(
std::static_pointer_cast<T>(value.get_ptr())) {}
1260 OptLink(OptLink<S> &&value) : val(
std::static_pointer_cast<T>(
std::move(value.get_ptr()))) {}
1266 void set(
const Maybe<S> &value) {
1267 val = std::static_pointer_cast<T>(value.get_ptr());
1274 OptLink &operator=(
const Maybe<S> &value) {
1283 void set(Maybe<S> &&value) {
1284 val = std::static_pointer_cast<T>(std::move(value.get_ptr()));
1291 OptLink &operator=(Maybe<S> &&value) {
1292 set<S>(std::move(value));
1306 virtual bool empty()
const {
1307 return val.expired();
1313 size_t size()
const {
1314 return val.expired() ? 0 : 1;
1322 if (val.expired()) {
1324 std::string(
"dereferencing empty or expired (Opt)Link object of type ") +
1328 return *(val.lock());
1350 if (val.expired()) {
1351 throw OutOfRange(
"dereferencing empty or expired (Opt)Link object");
1353 return *(val.lock());
1359 T &operator*()
const {
1366 T *operator->()
const {
1373 std::shared_ptr<T> get_ptr()
const {
1383 Maybe<S> as()
const {
1384 return Maybe<S>(std::dynamic_pointer_cast<S>(val.lock()));
1390 Maybe<T> as_mut()
const {
1391 return Maybe<T>(val.lock());
1397 Maybe<const T> as_const()
const {
1398 return Maybe<const T>(std::const_pointer_cast<
const T>(val.lock()));
1405 void visit(V &visitor) {
1406 if (!val.expired()) {
1407 val.lock()->visit(visitor);
1415 bool equals(
const OptLink &rhs)
const {
1416 return get_ptr() == rhs.get_ptr();
1422 bool operator==(
const OptLink &rhs)
const {
1423 return get_ptr() == rhs.get_ptr();
1429 inline bool operator!=(
const OptLink &rhs)
const {
1430 return !(*
this == rhs);
1436 bool operator>(
const OptLink &rhs)
const {
1437 return get_ptr() > rhs.get_ptr();
1443 bool operator>=(
const OptLink &rhs)
const {
1444 return get_ptr() >= rhs.get_ptr();
1450 bool operator<(
const OptLink &rhs)
const {
1451 return get_ptr() < rhs.get_ptr();
1457 bool operator<=(
const OptLink &rhs)
const {
1458 return get_ptr() <= rhs.get_ptr();
1465 bool links_to(
const Maybe<S> target) {
1466 return get_ptr() == std::dynamic_pointer_cast<T>(target.get_ptr());
1475 void find_reachable(PointerMap &map)
const override {
1489 void check_complete(
const PointerMap &map)
const override {
1490 if (!this->empty()) {
1500 virtual std::string serdes_edge_type()
const {
1507 void set_void_ptr(
const std::shared_ptr<void> &ptr)
override {
1508 val = std::static_pointer_cast<T>(ptr);
1517 void deserialize(
const cbor::MapReader &map, IdentifierMap &ids) {
1522 if (map.at(
"@T").as_string() != serdes_edge_type()) {
1523 throw RuntimeError(
"Schema validation failed: unexpected edge type");
1533 void serialize(cbor::MapWriter &map,
const PointerMap &ids)
const {
1534 map.append_string(
"@T", serdes_edge_type());
1535 map.append_int(
"@l", ids.get(*
this));
1542 OptLink(
const cbor::MapReader &map, IdentifierMap &ids) : val() {
1543 deserialize(map, ids);
1564 Link(
const Maybe<S> &value) :
OptLink<T>(value) {}
1576 Link(
const OptLink<S> &value) :
OptLink<T>(value) {}
1594 void check_complete(
const PointerMap &map)
const override {
1595 if (this->empty()) {
1596 std::ostringstream ss{};
1597 ss <<
"'Link' edge of type " <<
typeid(T).name() <<
" is empty";
1598 throw NotWellFormed(ss.str());
1608 std::string serdes_edge_type()
const override {
1618 Link(
const cbor::MapReader &map, IdentifierMap &ids) :
OptLink<T>() {
1619 this->deserialize(map, ids);
1630 size_t PointerMap::add(
const Maybe<T> &ob) {
1631 return add_raw(reinterpret_cast<const void*>(ob.get_ptr().get()),
typeid(T).name());
1641 size_t PointerMap::add_ref(
const T &ob) {
1642 return add_raw(reinterpret_cast<const void*>(&ob),
typeid(T).name());
1651 size_t PointerMap::get(
const Maybe<T> &ob)
const {
1652 return get_raw(reinterpret_cast<const void*>(ob.get_ptr().get()),
typeid(T).name());
1661 size_t PointerMap::get(
const OptLink<T> &ob)
const {
1662 return get_raw(reinterpret_cast<const void*>(ob.get_ptr().get()),
typeid(T).name());
1671 size_t PointerMap::get_ref(
const T &ob)
const {
1672 return get_raw(reinterpret_cast<const void*>(&ob),
typeid(T).name());
1679 void serialize(
const Maybe<T> tree, std::ostream &stream) {
1680 tree::cbor::Writer writer{stream};
1682 tree.find_reachable(ids);
1683 tree.check_complete(ids);
1684 auto map = writer.start();
1685 tree.serialize(map, ids);
1693 std::string serialize(
const Maybe<T> tree) {
1694 std::ostringstream stream{};
1695 serialize<T>(tree, stream);
1696 return stream.str();
1703 void serialize_file(
const Maybe<T> tree,
const std::string &filename) {
1704 serialize<T>(tree, std::ofstream(filename));
1711 Maybe<T> deserialize(
const std::string &cbor) {
1712 cbor::Reader reader{cbor};
1713 IdentifierMap ids{};
1714 Maybe<T> tree{reader.as_map(), ids};
1715 ids.restore_links();
1716 tree.check_well_formed();
1724 Maybe<T> deserialize(std::istream &stream) {
1725 std::ostringstream ss;
1726 ss << stream.rdbuf();
1727 return deserialize<T>(ss.str());
1734 Maybe<T> deserialize_file(
const std::string &&filename) {
1735 return deserialize<T>(std::ifstream(filename));
Link to zero or one nodes elsewhere in the tree.
Link to exactly one node elsewhere in the tree.