diff --git a/src/static_schema.cpp b/src/static_schema.cpp
index 2f1dcb2..082d03b 100644
--- a/src/static_schema.cpp
+++ b/src/static_schema.cpp
@@ -135,19 +135,28 @@
     return boost::get<yang::leaf>(children(locationString).at(node)).m_type;
 }
 
-std::set<std::string> StaticSchema::availableNodes(const boost::variant<dataPath_, schemaPath_, module_>& path, const Recursion recursion) const
+ModuleNodePair splitModuleNode(const std::string& input)
+{
+    auto colonLocation = input.find_first_of(':');
+    if (colonLocation != std::string::npos) {
+        return ModuleNodePair{input.substr(0, colonLocation), input.substr(colonLocation + 1)};
+    }
+    throw std::logic_error("Tried to split a string without a colon (StaticSchema node names should always be stored with prefixes)");
+}
+
+std::set<ModuleNodePair> StaticSchema::availableNodes(const boost::variant<dataPath_, schemaPath_, module_>& path, const Recursion recursion) const
 {
     if (recursion == Recursion::Recursive) {
         throw std::logic_error("Recursive StaticSchema::availableNodes is not implemented. It shouldn't be used in tests.");
     }
 
-    std::set<std::string> res;
+    std::set<ModuleNodePair> res;
     if (path.type() == typeid(module_)) {
         auto topLevelNodes = m_nodes.at("");
         auto modulePlusColon = boost::get<module_>(path).m_name + ":";
         for (const auto& it : topLevelNodes) {
             if (boost::algorithm::starts_with(it.first, modulePlusColon)) {
-                res.insert(it.first);
+                res.insert(splitModuleNode(it.first));
             }
         }
         return res;
@@ -160,7 +169,9 @@
 
     auto childrenRef = children(locationString);
 
-    std::transform(childrenRef.begin(), childrenRef.end(), std::inserter(res, res.end()), [](auto it) { return it.first; });
+    std::transform(childrenRef.begin(), childrenRef.end(), std::inserter(res, res.end()), [](const auto& it) {
+        return splitModuleNode(it.first);
+    });
     return res;
 }