Object storing and retrieving using wildcard identifier

Question

I'm writing an interpreter for a scripting language which allows objects to:

• Have an alias
• Be referenced using a wildcard
• Contain child objects
• Combination of all three above

For example:

CreateWindow("win", ...);
CreateName("win/texes1", ...);
CreateName("win/texes2", ...);
CreateAlias("win/texes1", "wintexes");
CreateAlias("win/texes2", "wintexes2");
CreateTexture("@wintexes/tex1", ...);
CreateTexture("@wintexes/tex2", ...);
Delete("@wintexes/*"); // Deletes textures
Delete("@wintexes*"); // Deletes names
Delete("win");

Crazy, I know. It wasn't me who came up with it though.

In order to call the function on all objects intended to be affected by it, I came up with this code:

class ObjectHolder_t : private Holder<Object>
{
public:
    virtual ~ObjectHolder_t()
    {
    }

    Object* Read(const string& Handle)
    {
        string Leftover = Handle;
        string ObjHandle = ExtractObjHandle(Leftover);
        if (Leftover.empty())
            return Holder::Read(ObjHandle);
        return GetHolder(ObjHandle)->Read(Leftover);
    }

    void Write(const string& Handle, Object* pObject)
    {
        string Leftover = Handle;
        string ObjHandle = ExtractObjHandle(Leftover);
        if (Leftover.empty())
            Holder::Write(ObjHandle, pObject);
        else
            GetHolder(ObjHandle)->Write(Leftover, pObject);
    }

    template <class F>
    void Execute(const string& Handle, F Func)
    {
        string Leftover = Handle;
        string ObjHandle = ExtractObjHandle(Leftover);
        if (ObjHandle.back() == '*')
            ObjHandle.front() == '@' ? WildcardAlias(Leftover, ObjHandle, Func) : WildcardCache(Leftover, ObjHandle, Func);
        else
            Leftover.empty() ? Func(&Cache.find(ObjHandle)->second) : GetHolder(ObjHandle)->Execute(Leftover, Func);
    }

    void WriteAlias(const string& Handle, const string& Alias)
    {
        Aliases[Alias] = Handle;
    }

private:
    template <class F>
    void ExecuteSafe(const string& HolderHandle, const string& Handle, F Func)
    {
        if (ObjectHolder_t* pHolder = GetHolder(HolderHandle))
            pHolder->Execute(Handle, Func);
    }

    template <class F>
    void WildcardAlias(const string& Leftover, const string& ObjHandle, F Func)
    {
        std::regex Regex(Regexify(ObjHandle.substr(1)));
        for (auto i = Aliases.begin(); i != Aliases.end(); ++i)
            if (std::regex_match(i->first, Regex))
                Leftover.empty() ? Execute(i->second, Func) : ExecuteSafe(i->second, Leftover, Func);
    }

    template <class F>
    void WildcardCache(const string& Leftover, const string& ObjHandle, F Func)
    {
        std::regex Regex(Regexify(ObjHandle));
        for (auto i = Cache.begin(); i != Cache.end(); ++i)
            if (std::regex_match(i->first, Regex))
                Leftover.empty() ? Func(&i->second) : ExecuteSafe(i->first, Leftover, Func);
    }

    string Regexify(const string& Wildcard)
    {
        return string("^" + Wildcard.substr(0, Wildcard.size() - 1) + ".*");
    }

    string ExtractObjHandle(string& Handle)
    {
        // Name
        string ObjHandle;
        size_t Index = Handle.find('/');
        if (Index != string::npos)
        {
            ObjHandle = Handle.substr(0, Index);
            Handle = Handle.substr(Index + 1);
        }
        else
        {
            ObjHandle = Handle;
            Handle.clear();
        }
        // Alias
        if (ObjHandle.front() == '@' && ObjHandle.back() != '*')
        {
            Handle = Aliases[ObjHandle.substr(1)] + "/" + Handle;
            ObjHandle = ExtractObjHandle(Handle);
        }
        return ObjHandle;
    }

    ObjectHolder_t* GetHolder(const string& Handle)
    {
        return (ObjectHolder_t*)(Holder::Read(Handle));
    }

    map<string, string> Aliases;
};

Variable name Cache is a bit misleading here, but that's what I get for reusing Holder<T> which was intended for another purpose. Cache is actually std::map<std::string, Object*>.

struct MapDeleter
{
    template <class T> void operator() (T Data) { delete Data.second; }
};

template <class T>
struct Holder
{
    ~Holder()
    {
        for_each(Cache.begin(), Cache.end(), MapDeleter());
    }

    T* Read(const string& Path)
    {
        auto iter = Cache.find(Path);
        if (iter != Cache.end())
            return iter->second;
        return nullptr;
    }

    void Write(const string& Path, T* Data)
    {
        Cache[Path] = Data;
    }

    map<string, T*> Cache;
};

The code is used like this:

void NSBInterpreter::Move()
{
    string Handle = PopString();
    int32_t Time = PopInt();
    int32_t X = PopInt();
    int32_t Y = PopInt();
    /*int32_t Tempo = */PopInt();
    bool Wait = PopBool();

    ObjectHolder.Execute(Handle, [Time, X, Y] (Object** ppObject)
    {
        if (Texture* pTexture = dynamic_cast<Texture*>(*ppObject))
            pTexture->Move(Time, X, Y);
    });

    if (Wait)
        pContext->Wait(Time);
}

My concern with this code is that it is very complex and spaghetti recursive (although recursion isn't very deep so it won't crash) and I will probably forget how exactly it works by the time it needs fixing. Any thoughts on improving this?

Answer 1

This is an answer-length response to Mislav's comment, which asked two questions.

I'm not sure how is (13) supposed to work. One way would be to construct a list of objects and return it, but I guess that's not very efficient.

To be able to write

for (Object *pObject : ObjectHolder.Write(Handle)) {
   ...
}

we need to make ObjectHolder_t::Write() return an object with begin() and end() methods, which when called return iterator objects (implementing operator* and operator++) that do the right thing in context. That is, something like

#include <string>
#include <map>
#include <memory>
#include <regex>
#include <type_traits>

template<class Iter>
struct IterPair {
    Iter b_, e_;
    IterPair(Iter b, Iter e): b_(std::move(b)), e_(std::move(e)) {}
    Iter begin() const { return b_; }
    Iter end() const { return e_; }
};

template<class T>
struct Holder {
    using ptr_t = std::unique_ptr<T>;
    using cache_t = std::map<std::string, ptr_t>;
    cache_t cache_;

    template<bool WritingAllowed>
    class Iterator {
        using star_t = typename std::conditional<WritingAllowed, ptr_t, const ptr_t>::type;
        using ctor_t = typename std::conditional<WritingAllowed, cache_t, const cache_t>::type;
        using cur_t = typename std::conditional<WritingAllowed, typename cache_t::iterator, typename cache_t::const_iterator>::type;
        friend class Holder<T>;
        cur_t cur_, end_;
        std::regex rx_;
        explicit Iterator(ctor_t& map) : cur_(map.end()), end_(map.end()) {}
        explicit Iterator(ctor_t& map, std::regex rx) : cur_(map.begin()), end_(map.end()), rx_(std::move(rx)) {
            while (cur_ != end_ && !std::regex_match(cur_->first, rx_)) {
                ++cur_;
            }
        }
    public:
        star_t& operator*() const {
            return cur_->second;
        }
        Iterator& operator++() {
            do {
                ++cur_;
            } while (cur_ != end_ && !std::regex_match(cur_->first, rx_));
            return *this;
        }
        bool operator==(const Iterator& rhs) const { return cur_ == rhs.cur_; }
        bool operator!=(const Iterator& rhs) const { return cur_ != rhs.cur_; }
    };

    // for pedagogical purposes only
    Holder() {
        cache_.insert(std::make_pair("alpha", std::make_unique<int>(1)));
        cache_.insert(std::make_pair("beta", std::make_unique<int>(2)));
        cache_.insert(std::make_pair("gamma", std::make_unique<int>(3)));
        cache_.insert(std::make_pair("delta", std::make_unique<int>(4)));
    }

    IterPair<Iterator<false>> Read(const std::regex& path_regex) const {
        using Iter = Iterator<false>;
        return { Iter(cache_, path_regex), Iter(cache_) };
    }

    IterPair<Iterator<true>> Write(const std::regex& path_regex) {
        using Iter = Iterator<true>;
        return { Iter(cache_, path_regex), Iter(cache_) };
    }
};

#include <stdio.h>

int main()
{
    Holder<int> h;

    for (const std::unique_ptr<int>& pi : h.Read(std::regex(".*ta"))) {
        printf("%d\n", *pi);
    }
}

Remove the const in main() to see what kind of compiler error you get if you try to write to the result of a Read() call.

Another problem is that one specific Func is supposed to be able to delete the object...

I think you'll find that the iterator design removes this problem entirely:

void NSBInterpreter::Delete() {
    std::string Handle = PopString();

    for (std::unique_ptr<Object>& pObj : ObjectHolder.Write(Handle)) {
        if (NSBContext* pThread = dynamic_cast<NSBContext*>(pObj.get())) {
            RemoveThread(pThread);
        }
        pObj = nullptr;
    }
}

However, using your original "visitor" design, I would observe that the operation "delete this object" needs to be managed by the ObjectHolder itself, and therefore I would tend to implement the operation via a "manager" object passed in to the visitor function.

void NSBInterpreter::Delete() {
    std::string Handle = PopString();

    ObjectHolder.Execute(Handle, [this](Object** ppObject, ObjectHolder_t::Manager& mgr) {
        if (NSBContext* pThread = dynamic_cast<NSBContext*>(*ppObject)) {
            RemoveThread(pThread);
        }
        mgr.Delete(ppObject);  // or perhaps just mgr.DeleteCurrentObject();
    });
}

Answer 2

The code is a bit verbose, which makes it hard to review in a tiny StackOverflow window... but here are my thoughts. I'll start with the nitpicks and then see about bigger issues.

(1) You use unadorned string and map, which means you're relying on using namespace std;. Don't do that. It's Just Not Done in typical C++ code.

(2) ObjectHolder_t has a virtual destructor, which is nice, but it already inherits from Holder<T>, whose destructor isn't virtual. (It's private inheritance, so I guess that's sort-of okay... but again it's bad style. It sends up red flags for the reader (me), which wastes my time even if they're false alarms.)

Also, speaking of the verbosity of this code, it's good style to put those empty braces on a single line instead of spread over three lines. Use virtual ~Holder() {} or virtual ~Holder() = default;, and remove the now-redundant destructor from ObjectHolder_t.

(3) std::map is a code smell; code using it can usually be optimized by replacing it with std::unordered_map. Unless of course your algorithm requires that the map be sorted, in which case, I'd add a // comment explaining that, right at the point where the reader is going to be smelling that std::map.

(4) ExtractObjHandle mutates its argument, in addition to returning another string by value. That's a big smelly code smell, and indeed we can see that the one place you use this subroutine (in Read, Write, and Execute), you have to explicitly copy the argument string because you don't want the original to be mutated. The proper way to return a pair of strings from a method is to change the return type to std::pair<std::string, std::string>. At that point you can also consider changing the parameter type from const std::string& to std::string if it would eliminate an explicit copy operation.

(5) That MapDeleter cruft seems like a buggy reimplementation of std::unique_ptr: you're just looking for something that holds a pointer and deletes it when it's destroyed. You can safely make the substitution.

(6) In fact, this whole "cache" thing is a bit boned from the start, because the Read method allows a pointer to "escape" from the cache's map. The caller could store that pointer somewhere, and then the cache gets destroyed (via ~Holder), which destroys the pointed-to object... and you end up with undefined behavior the next time you try to access the object through the original pointer. To fix this, the textbook approach is to use std::shared_ptr to manage lifetimes, and the real-world approach is "don't do that then". I'll assume your code doesn't do that, and that returning raw pointers to managed objects is totally fine by you.

(7) Nitpick: constify your const methods.

(8) Another nitpick: prefer Handle.npos to std::string::npos; it's just one fewer thing to worry about whether you matched up the types correctly. Modern C++ is quickly moving in the direction of "generic programming", which in a nutshell means never having to explicitly write out your data types if you don't need to. See also Herb Sutter's concept of "Almost Always Auto".

(9) In Regexify, you return string(...); where ... represents an expression of type string. The correct idiom here is simply return ...;. The former means "Evaluate ..., move-construct another string from it, and then move-construct the return value from that string." (The last move-construction may be elided.) As opposed to return ...;, which means "Evaluate ..., and then move-construct the return value from it." (The last move-construction may be elided.)

So let's see, what are we left with...?

template <class T> struct Holder
{
    T* Read(const std::string& Path) const {
        auto iter = Cache.find(Path);
        return iter == Cache.end() ? nullptr : iter->second.get();
    }

    void Write(const std::string& Path, T* Data) {
        Cache[Path] = std::unique_ptr<T>(Data);
    }

    virtual ~Holder() = default;

    std::unordered_map<std::string, std::unique_ptr<T>> Cache;
};

class ObjectHolder_t : private Holder<Object>
{
public:
    Object* Read(const std::string& Handle) {
        std::string ObjHandle, Leftover;
        std::tie(ObjHandle, Leftover) = ExtractObjHandle(Handle);
        if (Leftover.empty())
            return Holder::Read(ObjHandle);
        return GetHolder(ObjHandle)->Read(Leftover);
    }

    void Write(const string& Handle, Object* pObject) {
        std::string ObjHandle, Leftover;
        std::tie(ObjHandle, Leftover) = ExtractObjHandle(Handle);
        if (Leftover.empty())
            Holder::Write(ObjHandle, pObject);
        else
            GetHolder(ObjHandle)->Write(Leftover, pObject);
    }

    template <class F>
    void Execute(const string& Handle, F Func) {
        std::string ObjHandle, Leftover;
        std::tie(ObjHandle, Leftover) = ExtractObjHandle(Handle);
        if (ObjHandle.back() == '*') {
            ObjHandle.front() == '@' ? WildcardAlias(Leftover, ObjHandle, Func) : WildcardCache(Leftover, ObjHandle, Func);
        } else {
            Leftover.empty() ? Func(&Cache.find(ObjHandle)->second) : GetHolder(ObjHandle)->Execute(Leftover, Func);
        }
    }

    void WriteAlias(const std::string& Handle, const std::string& Alias) {
        Aliases[Alias] = Handle;
    }

private:
    template <class F>
    void ExecuteSafe(const string& HolderHandle, const string& Handle, F Func)
    {
        if (ObjectHolder_t* pHolder = GetHolder(HolderHandle))
            pHolder->Execute(Handle, Func);
    }

    template <class F>
    void WildcardAlias(const string& Leftover, const string& ObjHandle, F Func)
    {
        std::regex Regex(Regexify(ObjHandle.substr(1)));
        for (auto i = Aliases.begin(); i != Aliases.end(); ++i)
            if (std::regex_match(i->first, Regex))
                Leftover.empty() ? Execute(i->second, Func) : ExecuteSafe(i->second, Leftover, Func);
    }

    template <class F>
    void WildcardCache(const string& Leftover, const string& ObjHandle, F Func)
    {
        std::regex Regex(Regexify(ObjHandle));
        for (auto i = Cache.begin(); i != Cache.end(); ++i)
            if (std::regex_match(i->first, Regex))
                Leftover.empty() ? Func(&i->second) : ExecuteSafe(i->first, Leftover, Func);
    }

    std::string Regexify(const std::string& Wildcard)
    {
        return "^" + Wildcard.substr(0, Wildcard.size() - 1) + ".*";
    }

    std::pair<std::string, std::string> ExtractObjHandle(const std::string& Handle)
    {
        std::pair<std::string, std::string> Result;
        size_t Index = Handle.find('/');
        if (Index != Handle.npos) {
            Result.first = Handle.substr(0, Index);
            Result.second = Handle.substr(Index + 1);
        } else {
            Result.first = Handle;
            Result.second.clear();
        }
        std::string& ObjHandle = Result.first;
        if (ObjHandle.front() == '@' && ObjHandle.back() != '*') {
            Result.second = Aliases[ObjHandle.substr(1)] + "/" + Result.second;
            ObjHandle = ExtractObjHandle(Result.second);
        }
        return Result;
    }

    ObjectHolder_t* GetHolder(const std::string& Handle)
    {
        return (ObjectHolder_t*)(Holder::Read(Handle));
    }

    std::unordered_map<std::string, std::string> Aliases;
};

...I didn't get all the way through the code, but hopefully this gives you some ideas and maybe I'll do a second round later.

Parting thoughts:

(10) What if function F throws an exception – what guarantees does your code provide?

(11) What is function F supposed to look like, anyway? A block comment explaining the expected input would be nice. (You should be aware of std::function, but there are perfectly valid reasons not to use it in a lot of code. Cough efficiency cough.)

(12) The expression Func(&Cache.find(ObjHandle)->second) sends up red flags: what would happen if ObjHandle weren't in the Cache? What if Cache.find(ObjHandle) returned nullptr? Et cetera. I'd prefer to see such a complicated raw-pointery expression broken down into simple steps, with each step checked for failure before proceeding to the next step.

(13) A major architectural suggestion: Consider trying a complete rewrite, where instead of passing F Func all the way down the stack, you instead make Read and Write return pairs of iterators begin, end so that your existing caller

ObjectHolder.Execute(Handle, [Time, X, Y] (Object** ppObject)
{
    if (Texture* pTexture = dynamic_cast<Texture*>(*ppObject))
        pTexture->Move(Time, X, Y);
});

ends up looking more like

for (Object *pObject : ObjectHolder.Write(Handle)) {
    if (Texture *pTexture = dynamic_cast<Texture*>(pObject)) {
        pTexture->Move(Time, X, Y);
    }
}

That would be idiomatic C++11 (except for the smelly use of dynamic_cast, of course), and it's not significantly harder than what you're doing now. Give it a try and post a comment if you do! :)