From 648ca7febe4f09c663386ee2ea610d8ab150e053 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Roman=20Smr=C5=BE?= Date: Sun, 29 Oct 2023 21:51:17 +0100 Subject: Identity extension data --- include/erebos/identity.h | 6 +- src/identity.cpp | 265 ++++++++++++++++++++++++++++++++++++++-------- src/identity.h | 58 ++++++++-- 3 files changed, 276 insertions(+), 53 deletions(-) diff --git a/include/erebos/identity.h b/include/erebos/identity.h index 336a18a..7829361 100644 --- a/include/erebos/identity.h +++ b/include/erebos/identity.h @@ -10,6 +10,7 @@ using std::vector; template class Signed; struct IdentityData; +struct StoredIdentityPart; class Identity { @@ -22,9 +23,11 @@ public: static std::optional load(const Ref &); static std::optional load(const std::vector &); static std::optional load(const std::vector>> &); + static std::optional load(const std::vector &); std::vector store() const; std::vector store(const Storage & st) const; - const vector>> & data() const; + vector>> data() const; + vector extData() const; std::optional name() const; std::optional owner() const; @@ -59,6 +62,7 @@ public: static Builder create(const Storage &); Builder modify() const; Identity update(const vector>> &) const; + Identity update(const vector &) const; private: struct Priv; diff --git a/src/identity.cpp b/src/identity.cpp index fc62995..f2912c5 100644 --- a/src/identity.cpp +++ b/src/identity.cpp @@ -9,9 +9,14 @@ using namespace erebos; using std::async; +using std::get_if; using std::nullopt; using std::runtime_error; using std::set; +using std::visit; + +template +inline constexpr bool always_false_v = false; DEFINE_SHARED_TYPE(optional, "0c6c1fe0-f2d7-4891-926b-c332449f7871", @@ -32,16 +37,27 @@ optional Identity::load(const Ref & ref) optional Identity::load(const vector & refs) { - vector>> data; + vector data; data.reserve(refs.size()); for (const auto & ref : refs) - data.push_back(Stored>::load(ref)); + data.push_back(StoredIdentityPart::load(ref)); return load(data); } optional Identity::load(const vector>> & data) +{ + vector parts; + parts.reserve(data.size()); + + for (const auto & d : data) + parts.emplace_back(d); + + return load(parts); +} + +optional Identity::load(const vector & data) { if (auto ptr = Priv::validate(data)) return Identity(ptr); @@ -66,7 +82,17 @@ vector Identity::store(const Storage & st) const return res; } -const vector>> & Identity::data() const +vector>> Identity::data() const +{ + vector>> base; + base.reserve(p->data.size()); + + for (const auto & d : p->data) + base.push_back(d.base()); + return base; +} + +vector Identity::extData() const { return p->data; } @@ -90,7 +116,7 @@ const Identity & Identity::finalOwner() const Stored Identity::keyIdentity() const { - return p->data[0]->data->keyIdentity; + return p->data[0].base()->data->keyIdentity; } Stored Identity::keyMessage() const @@ -101,8 +127,8 @@ Stored Identity::keyMessage() const bool Identity::sameAs(const Identity & other) const { // TODO: proper identity check - return p->data[0]->data->keyIdentity == - other.p->data[0]->data->keyIdentity; + return p->data[0].base()->data->keyIdentity == + other.p->data[0].base()->data->keyIdentity; } bool Identity::operator==(const Identity & other) const @@ -154,28 +180,53 @@ Identity::Builder Identity::modify() const { return Builder (new Builder::Priv { .storage = p->data[0].ref().storage(), - .prev = p->data, - .keyIdentity = p->data[0]->data->keyIdentity, - .keyMessage = p->data[0]->data->keyMessage, + .prev = data(), + .keyIdentity = p->data[0].base()->data->keyIdentity, + .keyMessage = p->data[0].base()->data->keyMessage, }); } Identity Identity::update(const vector>> & updates) const { - vector>> ndata = p->data; - vector>> ownerUpdates = p->updates; + vector eupdates; + eupdates.reserve(updates.size()); + for (const auto & u : updates) + eupdates.emplace_back(u); + return update(eupdates); +} - for (const auto & u : updates) { - vector>> tmp = p->data; - tmp.push_back(u); +static bool intersectsRoots(const vector & x, const vector & y) +{ + for (size_t i = 0, j = 0; + i < x.size() && j < y.size(); ) { + if (x[i] == y[j]) + return true; + if (x[i] < y[j]) + i++; + else + j++; + } + return false; +} - size_t tmp_size = tmp.size(); - filterAncestors(tmp); +Identity Identity::update(const vector & updates) const +{ + vector ndata = p->data; + vector ownerUpdates = p->updates; - if (tmp.size() < tmp_size) - ndata.push_back(u); + for (const auto & u : updates) { + bool isOur = false; + for (const auto & d : p->data) { + if (intersectsRoots(u.roots(), d.roots())) { + isOur = true; + break; + } + } + + if (isOur) + ndata.emplace_back(u); else - ownerUpdates.push_back(u); + ownerUpdates.emplace_back(u); } filterAncestors(ndata); @@ -200,7 +251,7 @@ Identity Identity::Builder::commit() const .prev = p->prev, .name = p->name, .owner = p->owner && p->owner->p->data.size() == 1 ? - optional(p->owner->p->data[0]) : nullopt, + optional(p->owner->p->data[0].base()) : nullopt, .keyIdentity = p->keyIdentity, .keyMessage = p->keyMessage, }); @@ -217,7 +268,7 @@ Identity Identity::Builder::commit() const throw runtime_error("failed to load secret key"); } - auto p = Identity::Priv::validate({ sdata }); + auto p = Identity::Priv::validate({ StoredIdentityPart(sdata) }); if (!p) throw runtime_error("failed to validate committed identity"); @@ -273,34 +324,158 @@ Ref IdentityData::store(const Storage & st) const return st.storeObject(Record(std::move(items))); } -bool Identity::Priv::verifySignatures(const Stored> & sdata) +IdentityExtension IdentityExtension::load(const Ref & ref) +{ + if (auto rec = ref->asRecord()) { + if (auto base = rec->item("SBASE").as>()) { + vector prev; + for (const auto & r : rec->items("SPREV").asRef()) + prev.push_back(StoredIdentityPart::load(r)); + + auto ownerRef = rec->item("owner").asRef(); + return IdentityExtension { + .base = *base, + .prev = move(prev), + .name = rec->item("name").asText(), + .owner = ownerRef ? optional(StoredIdentityPart::load(*ownerRef)) : nullopt, + }; + } + } + + return IdentityExtension { + .base = Stored>::load(ref.storage().zref()), + .prev = {}, + .name = nullopt, + .owner = nullopt, + }; +} + +StoredIdentityPart StoredIdentityPart::load(const Ref & ref) { - if (!sdata->isSignedBy(sdata->data->keyIdentity)) + if (auto srec = ref->asRecord()) { + if (auto sref = srec->item("SDATA").asRef()) { + if (auto rec = (*sref)->asRecord()) { + if (rec->item("SBASE")) { + return StoredIdentityPart(Stored>::load(ref)); + } + } + } + } + + return StoredIdentityPart(Stored>::load(ref)); +} + +Ref StoredIdentityPart::store(const Storage & st) const +{ + return visit([&](auto && p) { + return p.store(st); + }, part); +} + +const Ref & StoredIdentityPart::ref() const +{ + return visit([&](auto && p) -> auto const & { + return p.ref(); + }, part); +} + +const Stored> & StoredIdentityPart::base() const +{ + return visit([&](auto && p) -> auto const & { + using T = std::decay_t; + if constexpr (std::is_same_v>>) + return p; + else if constexpr (std::is_same_v>>) + return p->data->base; + else + static_assert(always_false_v, "non-exhaustive visitor!"); + }, part); +} + +vector StoredIdentityPart::previous() const +{ + return visit([&](auto && p) { + using T = std::decay_t; + if constexpr (std::is_same_v>>) { + vector res; + res.reserve(p->data->prev.size()); + for (const auto & x : p->data->prev) + res.emplace_back(x); + return res; + + } else if constexpr (std::is_same_v>>) { + vector res; + res.reserve(1 + p->data->prev.size()); + res.emplace_back(p->data->base); + for (const auto & x : p->data->prev) + res.push_back(x); + return res; + + } else { + static_assert(always_false_v, "non-exhaustive visitor!"); + } + }, part); +} + +vector StoredIdentityPart::roots() const +{ + return visit([&](auto && p) { + return p.roots(); + }, part); +} + +optional StoredIdentityPart::name() const +{ + return visit([&](auto && p) { + return p->data->name; + }, part); +} + +optional StoredIdentityPart::owner() const +{ + return visit([&](auto && p) -> optional { + if (p->data->owner) + return StoredIdentityPart(p->data->owner.value()); + return nullopt; + }, part); +} + +bool StoredIdentityPart::isSignedBy(const Stored & key) const +{ + return visit([&](auto && p) { + return p->isSignedBy(key); + }, part); +} + + +bool Identity::Priv::verifySignatures(const StoredIdentityPart & sdata) +{ + if (!sdata.isSignedBy(sdata.base()->data->keyIdentity)) return false; - for (const auto & p : sdata->data->prev) - if (!sdata->isSignedBy(p->data->keyIdentity)) + for (const auto & p : sdata.previous()) + if (!sdata.isSignedBy(p.base()->data->keyIdentity)) return false; - if (sdata->data->owner && - !sdata->isSignedBy(sdata->data->owner.value()->data->keyIdentity)) - return false; + if (auto owner = sdata.owner()) + if (!sdata.isSignedBy(owner->base()->data->keyIdentity)) + return false; - for (const auto & p : sdata->data->prev) + for (const auto & p : sdata.previous()) if (!verifySignatures(p)) return false; return true; } -shared_ptr Identity::Priv::validate(const vector>> & sdata) +shared_ptr Identity::Priv::validate(const vector & sdata) { for (const auto & d : sdata) if (!verifySignatures(d)) return nullptr; auto keyMessageItem = lookupProperty(sdata, [] - (const IdentityData & d) { return d.keyMessage.has_value(); }); + (const StoredIdentityPart & d) { return d.base()->data->keyMessage.has_value(); }); if (!keyMessageItem) return nullptr; @@ -309,56 +484,56 @@ shared_ptr Identity::Priv::validate(const vectorkeyMessage.value(), + .keyMessage = keyMessageItem->base()->data->keyMessage.value(), }; shared_ptr ret(p); auto ownerProp = lookupProperty(sdata, [] - (const IdentityData & d) { return d.owner.has_value(); }); + (const StoredIdentityPart & d) { return d.owner().has_value(); }); if (ownerProp) { - auto owner = validate({ *ownerProp.value()->owner }); + auto owner = validate({ ownerProp->owner().value() }); if (!owner) return nullptr; p->owner.emplace(Identity(owner)); } p->name = async(std::launch::deferred, [p] () -> optional { - if (auto d = lookupProperty(p->data, [] (const IdentityData & d) { return d.name.has_value(); })) - return d.value()->name; + if (auto d = lookupProperty(p->data, [] (const StoredIdentityPart & d) { return d.name().has_value(); })) + return d->name(); return nullopt; }); return ret; } -optional> Identity::Priv::lookupProperty( - const vector>> & data, - function sel) +optional Identity::Priv::lookupProperty( + const vector & data, + function sel) { - set>> current, prop_heads; + set current, prop_heads; for (const auto & d : data) current.insert(d); while (!current.empty()) { - Stored> sdata = + StoredIdentityPart sdata = current.extract(current.begin()).value(); - if (sel(*sdata->data)) + if (sel(sdata)) prop_heads.insert(sdata); else - for (const auto & p : sdata->data->prev) + for (const auto & p : sdata.previous()) current.insert(p); } for (auto x = prop_heads.begin(); x != prop_heads.end(); x++) for (auto y = prop_heads.begin(); y != prop_heads.end();) - if (y != x && y->precedes(*x)) + if (y != x && precedes(*y, *x)) y = prop_heads.erase(y); else y++; if (prop_heads.begin() != prop_heads.end()) - return (*prop_heads.begin())->data; + return *prop_heads.begin(); return nullopt; } diff --git a/src/identity.h b/src/identity.h index 4b61c66..c3d9e2c 100644 --- a/src/identity.h +++ b/src/identity.h @@ -4,15 +4,48 @@ #include "pubkey.h" #include +#include using std::function; using std::optional; using std::shared_future; using std::string; +using std::variant; using std::vector; namespace erebos { +struct IdentityData; +struct IdentityExtension; + +struct StoredIdentityPart +{ + using Part = variant< + Stored>, + Stored>>; + + StoredIdentityPart(Part p): part(move(p)) {} + + static StoredIdentityPart load(const Ref &); + Ref store(const Storage & st) const; + + bool operator==(const StoredIdentityPart & other) const + { return part == other.part; } + bool operator<(const StoredIdentityPart & other) const + { return part < other.part; } + + const Ref & ref() const; + const Stored> & base() const; + + vector previous() const; + vector roots() const; + optional name() const; + optional owner() const; + bool isSignedBy(const Stored &) const; + + Part part; +}; + struct IdentityData { static IdentityData load(const Ref &); @@ -25,19 +58,30 @@ struct IdentityData const optional> keyMessage; }; +struct IdentityExtension +{ + static IdentityExtension load(const Ref &); + Ref store(const Storage & st) const; + + const Stored> base; + const vector prev; + const optional name; + const optional owner; +}; + struct Identity::Priv { - vector>> data; - vector>> updates; + vector data; + vector updates; shared_future> name; optional owner; Stored keyMessage; - static bool verifySignatures(const Stored> & sdata); - static shared_ptr validate(const vector>> & sdata); - static optional> lookupProperty( - const vector>> & data, - function sel); + static bool verifySignatures(const StoredIdentityPart & sdata); + static shared_ptr validate(const vector & sdata); + static optional lookupProperty( + const vector & data, + function sel); }; struct Identity::Builder::Priv -- cgit v1.2.3