diff --git a/tools/versioner/src/DeclarationDatabase.h b/tools/versioner/src/DeclarationDatabase.h
index 2b462bd..ac5de27 100644
--- a/tools/versioner/src/DeclarationDatabase.h
+++ b/tools/versioner/src/DeclarationDatabase.h
@@ -18,6 +18,7 @@
 
 #include <iostream>
 #include <map>
+#include <mutex>
 #include <set>
 #include <sstream>
 #include <string>
@@ -25,27 +26,22 @@
 
 #include <llvm/ADT/StringRef.h>
 
+#include "Arch.h"
 #include "Utils.h"
 
+namespace clang {
+class ASTUnit;
+class Decl;
+}
+
 enum class DeclarationType {
   function,
   variable,
   inconsistent,
 };
 
-static const char* declarationTypeName(DeclarationType type) {
-  switch (type) {
-    case DeclarationType::function:
-      return "function";
-    case DeclarationType::variable:
-      return "variable";
-    case DeclarationType::inconsistent:
-      return "inconsistent";
-  }
-}
-
 struct CompilationType {
-  std::string arch;
+  Arch arch;
   int api_level;
 
  private:
@@ -61,155 +57,181 @@
   bool operator==(const CompilationType& other) const {
     return tie() == other.tie();
   }
-
-  std::string describe() const {
-    return arch + "-" + std::to_string(api_level);
-  }
 };
 
-struct DeclarationAvailability {
+std::string to_string(const CompilationType& type);
+
+struct AvailabilityValues {
+  bool future = false;
   int introduced = 0;
   int deprecated = 0;
   int obsoleted = 0;
 
-  void dump(std::ostream& out = std::cout) const {
-    out << describe();
+  bool empty() const {
+    return !(future || introduced || deprecated || obsoleted);
   }
 
+  bool operator==(const AvailabilityValues& rhs) const {
+    return std::tie(introduced, deprecated, obsoleted) ==
+           std::tie(rhs.introduced, rhs.deprecated, rhs.obsoleted);
+  }
+
+  bool operator!=(const AvailabilityValues& rhs) const {
+    return !(*this == rhs);
+  }
+};
+
+std::string to_string(const AvailabilityValues& av);
+
+struct DeclarationAvailability {
+  AvailabilityValues global_availability;
+  ArchMap<AvailabilityValues> arch_availability;
+
   bool empty() const {
-    return !(introduced || deprecated || obsoleted);
-  }
+    if (!global_availability.empty()) {
+      return false;
+    }
 
-  auto tie() const {
-    return std::tie(introduced, deprecated, obsoleted);
+    for (auto it : arch_availability) {
+      if (!it.second.empty()) {
+        return false;
+      }
+    }
+
+    return true;
   }
 
   bool operator==(const DeclarationAvailability& rhs) const {
-    return this->tie() == rhs.tie();
+    return std::tie(global_availability, arch_availability) ==
+           std::tie(rhs.global_availability, rhs.arch_availability);
   }
 
   bool operator!=(const DeclarationAvailability& rhs) const {
     return !(*this == rhs);
   }
 
-  std::string describe() const {
-    if (!(introduced || deprecated || obsoleted)) {
-      return "no availability";
-    }
-
-    std::stringstream out;
-    bool need_comma = false;
-    auto comma = [&out, &need_comma]() {
-      if (!need_comma) {
-        need_comma = true;
-        return;
-      }
-      out << ", ";
-    };
-
-    if (introduced != 0) {
-      comma();
-      out << "introduced = " << introduced;
-    }
-    if (deprecated != 0) {
-      comma();
-      out << "deprecated = " << deprecated;
-    }
-    if (obsoleted != 0) {
-      comma();
-      out << "obsoleted = " << obsoleted;
-    }
-
-    return out.str();
-  }
+  // Returns false if the availability declarations conflict.
+  bool merge(const DeclarationAvailability& other);
 };
 
-struct DeclarationLocation {
-  std::string filename;
-  unsigned line_number;
+std::string to_string(const DeclarationAvailability& decl_av);
+
+struct FileLocation {
+  unsigned line;
   unsigned column;
-  DeclarationType type;
-  bool is_extern;
-  bool is_definition;
-  DeclarationAvailability availability;
 
-  auto tie() const {
-    return std::tie(filename, line_number, column, type, is_extern, is_definition);
+  bool operator<(const FileLocation& rhs) const {
+    return std::tie(line, column) < std::tie(rhs.line, rhs.column);
   }
 
-  bool operator<(const DeclarationLocation& other) const {
-    return tie() < other.tie();
-  }
-
-  bool operator==(const DeclarationLocation& other) const {
-    return tie() == other.tie();
-  }
-
-  void dump(const std::string& base_path = "", std::ostream& out = std::cout) const {
-    const char* var_type = declarationTypeName(type);
-    const char* declaration_type = is_definition ? "definition" : "declaration";
-    const char* linkage = is_extern ? "extern" : "static";
-
-    std::string stripped_path;
-    if (llvm::StringRef(filename).startswith(base_path)) {
-      stripped_path = filename.substr(base_path.size());
-    } else {
-      stripped_path = filename;
-    }
-
-    out << "        " << linkage << " " << var_type << " " << declaration_type << " @ "
-        << stripped_path << ":" << line_number << ":" << column;
-
-    out << "\t[";
-    availability.dump(out);
-    out << "]\n";
+  bool operator==(const FileLocation& rhs) const {
+    return std::tie(line, column) == std::tie(rhs.line, rhs.column);
   }
 };
 
+struct Location {
+  std::string filename;
+  FileLocation start;
+  FileLocation end;
+
+  bool operator<(const Location& rhs) const {
+    return std::tie(filename, start, end) < std::tie(rhs.filename, rhs.start, rhs.end);
+  }
+};
+
+std::string to_string(const Location& loc);
+
 struct Declaration {
-  std::string name;
-  std::set<DeclarationLocation> locations;
+  Location location;
 
-  bool hasDefinition() const {
-    for (const auto& location : locations) {
-      if (location.is_definition) {
-        return true;
-      }
-    }
-    return false;
+  bool is_extern;
+  bool is_definition;
+  std::map<CompilationType, DeclarationAvailability> availability;
+
+  bool calculateAvailability(DeclarationAvailability* output) const;
+  bool operator<(const Declaration& rhs) const {
+    return location < rhs.location;
   }
 
-  DeclarationType type() const {
-    DeclarationType result = locations.begin()->type;
-    for (const DeclarationLocation& location : locations) {
-      if (location.type != result) {
-        result = DeclarationType::inconsistent;
-      }
-    }
-    return result;
-  }
+  void dump(const std::string& base_path = "", std::ostream& out = std::cout,
+            unsigned indent = 0) const {
+    std::string indent_str(indent, ' ');
+    out << indent_str;
 
-  void dump(const std::string& base_path = "", std::ostream& out = std::cout) const {
-    out << "    " << name << " declared in " << locations.size() << " locations:\n";
-    for (const DeclarationLocation& location : locations) {
-      location.dump(base_path, out);
+    if (is_extern) {
+      out << "extern";
+    } else {
+      out << "static";
+    }
+
+    if (is_definition) {
+      out << " definition";
+    } else {
+      out << " declaration";
+    }
+
+    out << " @ " << StripPrefix(location.filename, base_path).str() << ":" << location.start.line
+        << ":" << location.start.column;
+
+    if (!availability.empty()) {
+      DeclarationAvailability avail;
+
+      out << "\n" << indent_str << "  ";
+      if (!calculateAvailability(&avail)) {
+        out << "invalid availability";
+      } else {
+        out << to_string(avail);
+      }
     }
   }
 };
 
-namespace clang {
-class ASTUnit;
-}
+struct Symbol {
+  std::string name;
+  std::map<Location, Declaration> declarations;
 
-class HeaderDatabase {
- public:
-  std::map<std::string, Declaration> declarations;
+  bool calculateAvailability(DeclarationAvailability* output) const;
+  bool hasDeclaration(const CompilationType& type) const;
 
-  void parseAST(clang::ASTUnit* ast);
+  bool operator<(const Symbol& rhs) const {
+    return name < rhs.name;
+  }
+
+  bool operator==(const Symbol& rhs) const {
+    return name == rhs.name;
+  }
 
   void dump(const std::string& base_path = "", std::ostream& out = std::cout) const {
-    out << "HeaderDatabase contains " << declarations.size() << " declarations:\n";
-    for (const auto& pair : declarations) {
+    DeclarationAvailability availability;
+    bool valid_availability = calculateAvailability(&availability);
+    out << "  " << name << ": ";
+
+    if (valid_availability) {
+      out << to_string(availability);
+    } else {
+      out << "invalid";
+    }
+
+    out << "\n";
+
+    for (auto& it : declarations) {
+      it.second.dump(base_path, out, 4);
+      out << "\n";
+    }
+  }
+};
+
+class HeaderDatabase {
+  std::mutex mutex;
+
+ public:
+  std::map<std::string, Symbol> symbols;
+
+  void parseAST(CompilationType type, clang::ASTUnit* ast);
+
+  void dump(const std::string& base_path = "", std::ostream& out = std::cout) const {
+    out << "HeaderDatabase contains " << symbols.size() << " symbols:\n";
+    for (const auto& pair : symbols) {
       pair.second.dump(base_path, out);
     }
   }