WIP

.vscode/settings.json

@@ -1,5 +1,6 @@
 {
   "omnisharp.autoStart": false,
   "cmake.sourceDirectory": "${workspaceFolder}/swift",
-  "cmake.buildDirectory": "${workspaceFolder}/bazel-cmake-build"
+  "cmake.buildDirectory": "${workspaceFolder}/bazel-cmake-build",
+  "codeQL.githubDatabase.download": "never"
 }

cpp/ql/lib/experimental/buildless/ASTSig.qll

@@ -0,0 +1,88 @@
+import cpp
+
+/*
+    The syntax of a C++ program.
+*/
+signature module BuildlessASTSig
+{
+    class Node;
+    predicate nodeLocation(Node node, Location location);
+
+    // Parent/child relationship between AST nodes
+    predicate edge(Node parent, int index, Node child);
+
+    // Include graph
+    predicate userInclude(Node include, string path);
+    predicate systemInclude(Node include, string path);
+
+    // Namespaces
+    predicate namespace(Node ns);
+    predicate namespaceName(Node ns, string name);
+    predicate namespaceMember(Node ns, Node member);
+
+    // Functions
+    predicate function(Node fn);
+    predicate functionBody(Node fn, Node body);
+    predicate functionReturn(Node fn, Node returnType);
+    predicate functionName(Node fn, string name);
+    predicate functionParameter(Node fn, int i, Node parameterDecl);
+    predicate functionDefinition(Node fn);  // If a definition as opposed to a declaration
+
+    // Statements
+    predicate stmt(Node node);
+    predicate blockStmt(Node stmt);
+    predicate blockMember(Node stmt, int index, Node child);
+    predicate ifStmt(Node stmt, Node condition, Node thenBranch);
+    predicate ifStmt(Node tmt, Node condition, Node thenBranch, Node elseBranch);
+    predicate whileStmt(Node stmt, Node condition, Node body);
+    predicate doWhileStmt(Node stmt, Node condition, Node body);
+    predicate forStmt(Node stmt, Node init, Node condition, Node update, Node body);
+    predicate exprStmt(Node stmt, Node expr);
+    predicate returnStmt(Node stmt, Node expr);
+    predicate returnVoidStmt(Node stmt);
+    // etc
+
+    // Types
+    predicate type(Node type);
+    predicate ptrType(Node type, Node element);
+    predicate refType(Node type, Node element);
+    predicate constType(Node type, Node element);
+    predicate rvalueRefType(Node type, Node element);
+    predicate arrayType(Node type, Node element, Node size);
+    predicate arrayType(Node type, Node element);
+    predicate typename(Node node, string name);  // Any named type, including built-in types
+    predicate templated(Node node);
+    predicate typeDefinition(Node node);  // If a definition as opposed to a declaration
+
+    predicate classOrStructDefinition(Node node);
+    predicate classMember(Node classOrStruct, int child, Node member);
+
+    // Templates
+    predicate templateParameter(Node node, int i, Node parameter);
+    predicate typeParameter(Node templateParameter, Node type, Node parameter);
+    predicate typeParameterDefault(Node templateParameter, Node defaultTypeOrValue);
+
+    // Declarations
+    predicate variableDeclaration(Node decl);
+    predicate variableDeclarationType(Node decl, Node type);
+    predicate variableDeclarationEntry(Node decl, int index, Node entry);
+    predicate variableDeclarationEntryInitializer(Node entry, Node initializer);
+    predicate variableName(Node entry, string name);
+    predicate ptrEntry(Node entry, Node element);
+    predicate refEntry(Node entry, Node element);
+    predicate rvalueRefEntry(Node entry, Node element);
+    predicate arrayEntry(Node entry, Node element);  // ?? Size
+
+    // Expressions
+    predicate expression(Node node);
+    predicate prefixExpr(Node expr, string operator, Node operand);
+    predicate postfixExpr(Node expr, Node operand, string operator);
+    predicate binaryExpr(Node expr, Node lhs, string operator, Node rhs);
+    predicate castExpr(Node expr, Node type, Node operand);
+    predicate callExpr(Node call);
+    predicate callArgument(Node call, int i, Node arg);
+    predicate callReceiver(Node call, Node receiver);
+    predicate accessExpr(Node expr, string name);
+    predicate literal(Node expr, string value);
+    predicate stringLiteral(Node expr, string value);
+}

cpp/ql/lib/experimental/buildless/CompiledAST.qll

@@ -0,0 +1,304 @@
+import cpp
+import ASTSig
+
+module CompiledAST implements BuildlessASTSig {
+  private class SourceLocation extends Location {
+    SourceLocation() { not this.hasLocationInfo(_, 0, 0, 0, 0) }
+  }
+
+  private Type reachableType(Type type) {
+    result = type or
+    result = reachableType(type).stripTopLevelSpecifiers() or
+    result = reachableType(type).(PointerType).getBaseType() or
+    result = reachableType(type).(ReferenceType).getBaseType()
+  }
+
+  private class SourceDeclEntry extends DeclarationEntry {
+    SourceDeclEntry() {
+      not this.isAffectedByMacro() and
+      not this.isFromTemplateInstantiation(_) and
+      not this.isInMacroExpansion() and
+      not this.getDeclaration().isInMacroExpansion() and
+      this.getLocation() instanceof SourceLocation and
+      not this.(FunctionDeclarationEntry).getDeclaration().isCompilerGenerated()
+    }
+  }
+
+  private newtype TNode =
+    // TFunction(SourceLocation loc) { exists(Function f | f.getLocation() = loc) } or
+    TStatement(SourceLocation loc) { exists(Stmt s | s.getLocation() = loc) } or
+    TDeclaration(SourceDeclEntry decl) or
+    TExpression(SourceLocation loc) { exists(Expr e | e.getLocation() = loc) } or
+    TFunctionCallName(SourceLocation loc) { exists(FunctionCall c | c.getLocation() = loc) } or
+    TDeclarationType(SourceDeclEntry decl, Type type) { type = reachableType(decl.getType()) } or
+    TNamespaceDeclaration(NamespaceDeclarationEntry ns) { any() } or
+    TInclude(Include i)
+
+  class Node extends TNode {
+    string toString() { result = "node" }
+
+    SourceLocation getLocation() {
+      this = TStatement(result) or
+      result = this.getDeclaration().getLocation() or
+      this = TExpression(result) or
+      this = TFunctionCallName(result) or
+      result = this.getVariableDeclaration().getLocation() or
+      result = this.getNamespaceDeclaration().getLocation() or
+      result = this.getInclude().getLocation()
+    }
+
+    Include getInclude() { this = TInclude(result) }
+
+    Stmt getStmt() { this = TStatement(result.getLocation()) }
+
+    Function getFunction() {
+      result = this.getDeclaration().getDeclaration() and
+      not result.isFromTemplateInstantiation(_) and
+      not result.isCompilerGenerated()
+    }
+
+    SourceDeclEntry getDeclaration() { this = TDeclaration(result) }
+
+    NamespaceDeclarationEntry getNamespaceDeclaration() { this = TNamespaceDeclaration(result) }
+
+    Type getType() { this = TDeclarationType(_, result) }
+
+    SourceDeclEntry getVariableDeclaration() { this = TDeclarationType(result, _) }
+
+    Expr getExpr() { this = TExpression(result.getLocation()) }
+
+    FunctionCall getFunctionCallName() { this = TFunctionCallName(result.getLocation()) }
+  }
+
+  predicate nodeLocation(Node node, Location location) { location = node.getLocation() }
+
+  // Include graph
+  predicate userInclude(Node include, string path) {
+    exists(string head | head = include.getInclude().getHead() |
+      path = head.substring(1, head.length() - 1) and head.charAt(0) = "\""
+    )
+  }
+
+  predicate systemInclude(Node include, string path) {
+    exists(string head | head = include.getInclude().getHead() |
+      path = head.substring(1, head.length() - 1) and head.charAt(0) = "<"
+    )
+  }
+
+  // Functions
+  predicate function(Node fn) { exists(fn.getFunction()) }
+
+  predicate functionBody(Node fn, Node body) { body.getStmt() = fn.getFunction().getBlock() }
+
+  predicate functionReturn(Node fn, Node returnType) {
+    returnType.getVariableDeclaration() = fn.getDeclaration() and
+    fn.getDeclaration().(FunctionDeclarationEntry).getDeclaration().getType() = returnType.getType()
+  }
+
+  predicate functionName(Node fn, string name) { name = fn.getFunction().getName() }
+
+  predicate functionParameter(Node fn, int i, Node parameterDecl) {
+    functionParameter0(fn, i, parameterDecl) and
+    not exists(Node param2 | functionParameter0(fn, i, param2) |
+      param2.getLocation().getStartLine() < parameterDecl.getLocation().getStartLine()
+    )
+  }
+
+  pragma[nomagic]
+  private predicate functionParameter0(Node fn, int i, Node parameterDecl) {
+    fn.getFunction().getParameter(i).getADeclarationEntry() = parameterDecl.getDeclaration() and
+    fn.getLocation().getFile() = parameterDecl.getLocation().getFile() and
+    fn.getLocation().getStartLine() <= parameterDecl.getLocation().getStartLine()
+  }
+
+  // Statements
+  predicate stmt(Node node) { exists(node.getStmt()) }
+
+  predicate blockStmt(Node stmt) { stmt.getStmt() instanceof BlockStmt }
+
+  predicate blockMember(Node stmt, int index, Node child) {
+    child.getStmt() = stmt.getStmt().(BlockStmt).getChild(index)
+  }
+
+  predicate ifStmt(Node stmt, Node condition, Node thenBranch) { none() }
+
+  predicate ifStmt(Node tmt, Node condition, Node thenBranch, Node elseBranch) { none() }
+
+  predicate whileStmt(Node stmt, Node condition, Node body) { none() }
+
+  predicate doWhileStmt(Node stmt, Node condition, Node body) { none() }
+
+  predicate forStmt(Node stmt, Node init, Node condition, Node update, Node body) { none() }
+
+  predicate exprStmt(Node stmt, Node expr) { none() }
+
+  predicate returnStmt(Node stmt, Node expr) { none() }
+
+  predicate returnVoidStmt(Node stmt) { none() }
+
+  // etc
+  // Types
+  predicate ptrType(Node node, Node element) {
+    exists(PointerType type, SourceDeclEntry e |
+      node = TDeclarationType(e, type) and
+      element = TDeclarationType(e, type.getBaseType())
+    )
+  }
+
+  predicate refType(Node node, Node element) {
+    exists(ReferenceType type, SourceDeclEntry e |
+      node = TDeclarationType(e, type) and
+      element = TDeclarationType(e, type.getBaseType())
+    )
+  }
+
+  predicate rvalueRefType(Node type, Node element) { none() }
+
+  predicate arrayType(Node type, Node element, Node size) { none() }
+
+  predicate arrayType(Node type, Node element) { none() }
+
+  predicate typename(Node node, string name) {
+    exists(Class c | c = node.getDeclaration().getDeclaration() |
+      not c.isAnonymous() and c.getName() = name
+    )
+    or
+    name = node.getType().getName()
+  }
+
+  predicate templated(Node node) { none() }
+
+  predicate classOrStructDefinition(Node node) {
+    node.getDeclaration().getDeclaration() instanceof Class
+  }
+
+  predicate classMember(Node classOrStruct, int child, Node member) {
+    classOrStruct.getDeclaration().getDeclaration().(Class).getAMember() =
+      member.getDeclaration().getDeclaration() and
+    child = 0 and
+    classOrStruct.getLocation().getFile() = member.getLocation().getFile() // TODO: Disambiguate
+    // and not member.getDeclaration().getDeclaration() instanceof FriendDecl
+  }
+
+  // Templates
+  predicate templateParameter(Node node, int i, Node parameter) { none() }
+
+  predicate typeParameter(Node templateParameter, Node type, Node parameter) { none() }
+
+  predicate typeParameterDefault(Node templateParameter, Node defaultTypeOrValue) { none() }
+
+  // Declarations
+  predicate variableDeclaration(Node decl) {
+    decl.getDeclaration() instanceof VariableDeclarationEntry
+  }
+
+  pragma[nomagic]
+  private predicate variableDeclarationType2(Node decl, Node type) {
+    decl.getDeclaration() = type.getVariableDeclaration()
+  }
+
+  predicate variableDeclarationType(Node decl, Node type) {
+    variableDeclarationType2(decl, type) and
+    type.getType() = decl.getDeclaration().getType()
+  }
+
+  predicate variableDeclarationEntry(Node decl, int index, Node entry) { none() }
+
+  predicate variableDeclarationEntryInitializer(Node entry, Node initializer) { none() }
+
+  predicate variableName(Node decl, string name) {
+    decl.getDeclaration().(VariableDeclarationEntry).getName() = name
+  }
+
+  predicate ptrEntry(Node entry, Node element) { none() }
+
+  predicate refEntry(Node entry, Node element) { none() }
+
+  predicate rvalueRefEntry(Node entry, Node element) { none() }
+
+  predicate arrayEntry(Node entry, Node element) { none() }
+
+  // Expressions
+  predicate expression(Node node) { exists(node.getExpr()) or exists(node.getFunctionCallName()) }
+
+  predicate prefixExpr(Node expr, string operator, Node operand) { none() }
+
+  predicate postfixExpr(Node expr, Node operand, string operator) { none() }
+
+  predicate binaryExpr(Node expr, Node lhs, string operator, Node rhs) { none() }
+
+  predicate castExpr(Node expr, Node type, Node operand) { none() }
+
+  predicate callExpr(Node call) { call.getExpr() instanceof Call }
+
+  predicate callArgument(Node call, int i, Node arg) {
+    arg.getExpr() = call.getExpr().(Call).getArgument(i)
+  }
+
+  predicate callReceiver(Node call, Node receiver) {
+    receiver.getFunctionCallName() = call.getExpr()
+  }
+
+  predicate accessExpr(Node expr, string name) {
+    expr.getExpr().(VariableAccess).getTarget().getName() = name or
+    expr.getFunctionCallName().getTarget().getName() = name
+  }
+
+  predicate literal(Node expr, string value) { expr.getExpr().(Literal).toString() = value }
+
+  predicate stringLiteral(Node expr, string value) {
+    expr.getExpr().(StringLiteral).getValue() = value
+  }
+
+  predicate type(Node node) { node = TDeclarationType(_, _) }
+
+  predicate constType(Node node, Node element) {
+    exists(SpecifiedType type, SourceDeclEntry e |
+      node = TDeclarationType(e, type) and
+      element = TDeclarationType(e, type.getBaseType()) and
+      type.isConst()
+    )
+  }
+
+  predicate namespace(Node ns) { exists(ns.getNamespaceDeclaration()) }
+
+  predicate namespaceName(Node ns, string name) {
+    ns.getNamespaceDeclaration().getNamespace().getName() = name
+  }
+
+  pragma[nomagic]
+  private predicate namespaceNamespace(Node ns, Node child) {
+    ns.getNamespaceDeclaration().getNamespace().getAChildNamespace() =
+      child.getNamespaceDeclaration().getNamespace() and
+    ns.getLocation().getFile() = child.getLocation().getFile()
+  }
+
+  pragma[nomagic]
+  private predicate namespaceDecl(Node ns, Node child) {
+    child.getDeclaration().getDeclaration() =
+      ns.getNamespaceDeclaration().getNamespace().getADeclaration() and
+    ns.getLocation().getFile() = child.getLocation().getFile() and
+    ns.getLocation().getStartLine() <= child.getLocation().getStartLine()
+  }
+
+  predicate namespaceMember(Node ns, Node member) {
+    namespaceNamespace(ns, member) or
+    namespaceDecl(ns, member)
+  }
+
+  predicate edge(Node parent, int index, Node child) {
+    namespaceMember(parent, child) and index = 0
+    or
+    classMember(parent, index, child)
+    or
+    blockMember(parent, index, child)
+  }
+
+  predicate typeDefinition(Node node) {
+    node.getDeclaration().(TypeDeclarationEntry).isDefinition()
+  }
+
+  predicate functionDefinition(Node fn) {
+    fn.getDeclaration().(FunctionDeclarationEntry).isDefinition()
+  }
+}

cpp/ql/lib/experimental/buildless/Model.qll

@@ -0,0 +1,282 @@
+import AST
+
+module BuildlessModel<BuildlessASTSig Sig> {
+  module AST = BuildlessAST<Sig>;
+
+  private string getQualifiedName(AST::SourceNamespace ns) {
+    not exists(AST::SourceNamespace p | ns = p.getAChild()) and result = ns.getName()
+    or
+    exists(AST::SourceNamespace p | ns = p.getAChild() and ns != p |
+      result = getQualifiedName(p) + "::" + ns.getName()
+    )
+  }
+
+  private newtype TElement =
+    TNamespace(string fqn) { fqn = getQualifiedName(_) } or
+    TASTNode(AST::SourceElement node) { any() }
+
+    /*
+      Any compile-time concept that can be named.
+    */
+  class Entity extends string
+  {
+    bindingset[this] Entity() { any() }
+  }
+
+  /*
+    An entity that contains named members.
+  */
+  class Scope extends Entity
+  {
+    bindingset[this] Scope() { any() }
+
+    Member getAMember() { result = this.getAMember(_) }
+
+    abstract Member getAMember(string name);
+  }
+
+  /*
+    An entity that is a member of a scope.
+  */
+  class Member extends Entity
+  {
+    bindingset[this] Member() { any() }
+
+    abstract string getName();
+    abstract Scope getParent();
+  }
+
+  class Namespace2 extends Member, Scope
+  {
+    AST::SourceNamespace ns;
+
+    Namespace2() { this = "::" + getQualifiedName(ns) }
+
+    AST::SourceNamespace getAstNode() { result = ns }
+
+    override Namespace2 getParent() { result.getAstNode() = ns.getParent() }
+
+    override string getName() { result = ns.getName() }
+
+    override Member getAMember(string name) {
+      result = this.getMemberNamespace(name)
+      // !! Types
+    }
+
+    Namespace2 getMemberNamespace(string name) {
+      result.getParent() = this and result.getName() = name
+    }
+
+  }
+
+  class Type extends Member, Scope {
+    Type() { exists(SourceTypeDeclaration t | t.getMangledName() = this) }
+
+    AST::SourceType getAstNode() { result = this.getADeclaration().getSourceNode() }
+
+    // string toString() { result = "i am a type" }
+    override string getName() { result = this.getADeclaration().getName() }
+
+    Location getLocation() { result = this.getADefinition().getLocation() }
+
+    SourceTypeDeclaration getADeclaration() { result.getMangledName() = this }
+
+    SourceTypeDefinition getADefinition() { result.getMangledName() = this }
+
+    override Member getAMember(string name)
+    {
+      result = getMemberType(name)
+    }
+
+    Type getMemberType(string name)
+    {
+      none()
+    }
+
+    Namespace2 getParentNamespace() {
+      result.getAstNode() = this.getADeclaration().getParentNamespace()
+    }
+
+    Type getParentType() { result.getADeclaration() = this.getADeclaration().getParentType() }
+
+    override Scope getParent() { result = this.getParentNamespace() or result = this.getParentType() }
+
+    string getFullyQualifiedName() { result = this.getADeclaration().getFullyQualifiedName() }
+
+    Field getAField() { result.getParentType() = this }
+  }
+
+  private Type lookupNameInType(Type type, string name)
+  {
+    // Is the name a member of this type?
+
+    // Is the name in the same scope as the type?
+
+    // Is the name in global scope?
+
+    // TODO!
+    none()
+  }
+
+  class Field extends string {
+    Type containingType;
+    SourceTypeDefinition containingTypeDef;
+    AST::SourceVariableDeclaration fieldDef;
+
+    Field() {
+      containingType.getADefinition() = containingTypeDef and
+      fieldDef = containingTypeDef.getAField() and
+      this = containingTypeDef.getMangledName() + "::" + fieldDef.getName()
+    }
+
+    Location getLocation() { result = fieldDef.getLocation() }
+
+    Type getParentType() { result = containingType }
+
+    string getName() { result = fieldDef.getName() }
+
+    // TODO: The type of the field
+
+  }
+
+  class Element extends TElement {
+    string toString() { result = "element" }
+  }
+
+  class Namespace extends Element, TNamespace {
+    string getFullyQualifiedName() { this = TNamespace(result) }
+
+    override string toString() { result = "namespace " + this.getFullyQualifiedName() }
+
+    NamespaceDeclaration getADeclaration() { result.getNamespace() = this }
+  }
+
+  class SourceElement extends Element, TASTNode {
+    AST::SourceElement node;
+
+    SourceElement() { this = TASTNode(node) }
+
+    Location getLocation() { result = node.getLocation() }
+
+    AST::SourceElement getSourceNode() { result = node }
+  }
+
+  class SourceDeclaration extends SourceElement, TASTNode {
+    abstract SourceDeclaration getParent();
+
+    abstract string getName();
+
+    abstract string getMangledName();
+
+    abstract predicate isDefinition();
+  }
+
+  abstract class SourceDefinition extends SourceDeclaration { }
+
+  class NamespaceDeclaration extends SourceDeclaration {
+    AST::SourceNamespace ns;
+
+    NamespaceDeclaration() { ns = node }
+
+    override string getName() { result = ns.getName() }
+
+    Namespace getNamespace() { result.getFullyQualifiedName() = this.getFullyQualifiedName() }
+
+    override string toString() { result = "namespace " + this.getName() + " { ... }" }
+
+    override NamespaceDeclaration getParent() { result.getSourceNode() = node.getParent() }
+
+    string getFullyQualifiedName() {
+      if exists(this.getParent())
+      then result = this.getParent().getFullyQualifiedName() + "::" + this.getName()
+      else result = this.getName()
+    }
+
+    override string getMangledName() { result = "::" + this.getFullyQualifiedName() }
+
+    override predicate isDefinition() { any() }
+  }
+
+  class SourceTypeDeclaration extends SourceDeclaration {
+    AST::SourceTypeDefinition def;
+
+    SourceTypeDeclaration() { def = node }
+
+    override Location getLocation() { result = def.getLocation() }
+
+    override string toString() { result = "typename " + def.getName() }
+
+    string getFullyQualifiedName() {
+      if exists(this.getParentNamespace())
+      then result = this.getParentNamespace().getFullyQualifiedName() + "::" + this.getName()
+      else
+        if exists(this.getParentType())
+        then result = this.getParentType() + "::" + this.getName()
+        else result = this.getName()
+    }
+
+    NamespaceDeclaration getParentNamespace() { result.getSourceNode() = def.getParent() }
+
+    SourceTypeDeclaration getParentType() { result.getSourceNode() = def.getParent() }
+
+    override SourceDeclaration getParent() {
+      result = this.getParentNamespace() or result = this.getParentType()
+    }
+
+    override string getName() { result = def.getName() }
+
+    // Mangled name
+    override string getMangledName() {
+      if exists(this.getParent())
+      then result = this.getParent().getMangledName() + "::" + this.getName()
+      else result = "::" + this.getName()
+    }
+
+    override predicate isDefinition() { def.isDefinition() }
+
+    AST::SourceVariableDeclaration getAField() {
+      result = def.getAMember()
+    }
+  }
+
+  class SourceTypeDefinition extends SourceTypeDeclaration, SourceDefinition {
+    SourceTypeDefinition() { this.isDefinition() }
+  }
+
+  class SourceFunctionDeclaration extends SourceDeclaration {
+    AST::SourceFunction fn;
+
+    SourceFunctionDeclaration() { fn = node }
+
+    SourceTypeDeclaration getParentType() { result.getSourceNode() = fn.getParent() }
+
+    NamespaceDeclaration getParentNamespace() { result.getSourceNode() = fn.getParent() }
+
+    override SourceDeclaration getParent() {
+      result = this.getParentType() or result = this.getParentNamespace()
+    }
+
+    override string toString() { result = fn.getName() + "()" }
+
+    override Location getLocation() { result = fn.getLocation() }
+
+    override string getName() { result = fn.getName() }
+
+    override string getMangledName() {
+      if exists(this.getParent())
+      then result = this.getParent().getMangledName() + "::" + this.getName() + "()"
+      else result = "::" + this.getName() + "()"
+    }
+
+    override predicate isDefinition() { fn.isDefinition() }
+  }
+
+  class SourceFunctionDefinition extends SourceFunctionDeclaration, SourceDefinition {
+    SourceFunctionDefinition() { this.isDefinition() }
+  }
+
+  predicate invalidParent(SourceDeclaration decl) { decl.getParent+() = decl }
+}
+
+// For debugging in context
+module TestModel = BuildlessModel<CompiledAST>;

cpp/ql/lib/experimental/buildless/TODO.md

@@ -0,0 +1,46 @@
+Next:
+- [x] Namespaces
+- [ ] Unnamed class/struct/union and name mangling
+- [ ] Linker awareness is creating duplicates
+
+
+
+- Resolve the type of a local variable
+
+
+- [ ] Parent scopes - where are things declared
+    Parent class
+    Parent namespace
+    Parent function (for variable declarations and parameters)
+    Parent block (for blocks and statements)
+
+
+
+- [ ] Return type nodes
+- [ ] Construction of types
+- [ ] Construction of functions
+- [ ] Construction of Variables
+
+
+
+
+Names:
+- [x] Identify all function names
+- [x] Identify all parameter names
+- [x] Identify all variable declaration names
+- [x] Identify variable accesses
+
+Types:
+- [x] Locate user type definitions and typedefs
+- [x] Get the type of the parameter
+- [ ] Assign types to variable accesses
+
+Calls:
+- [x] Identify function call expressions
+- [x] Identify the "target" of a call in a trivial case.
+
+Overloads:
+
+Types:
+- [ ] Identify return types
+- [x] Identify parameter types and other declarations

cpp/ql/lib/experimental/buildless/ast.qll

@@ -0,0 +1,196 @@
+import CompiledAST
+import ASTSig
+
+module BuildlessAST<BuildlessASTSig AST> {
+  final class Node = AST::Node;
+
+  // Any node in the abstract syntax tree
+  class SourceElement extends Node {
+    Location getLocation() { AST::nodeLocation(this, result) }
+
+    string toString() { result = "element" }
+
+    SourceElement getParent() { AST::edge(result, _, this) }
+
+    SourceElement getChild(int i) { AST::edge(this, i, result) }
+
+    SourceElement getAChild() { result = this.getChild(_) }
+  }
+
+  bindingset[path]
+  private File getAnIncludeTarget(string path) {
+    exists(string p | p = result.toString() | path = p.suffix(p.length() - path.length()))
+  }
+
+  class Include extends SourceElement {
+    string path;
+
+    Include() { AST::userInclude(this, path) or AST::systemInclude(this, path) }
+
+    File getATarget() {
+      result = getAnIncludeTarget(path)
+      or
+      path.prefix(3) = "../" and result = getAnIncludeTarget(path.suffix(3))
+      or
+      path.prefix(2) = "./" and result = getAnIncludeTarget(path.suffix(2))
+    }
+
+    predicate isSystemInclude() { AST::systemInclude(this, _) }
+
+    predicate isUserInclude() { AST::userInclude(this, _) }
+
+    override string toString() {
+      this.isSystemInclude() and result = "#include <" + path + ">"
+      or
+      this.isUserInclude() and result = "#include \"" + path + "\""
+    }
+  }
+
+  abstract class SourceScope extends SourceElement { }
+
+  class SourceNamespace extends SourceScope, SourceDeclaration {
+    SourceNamespace() { AST::namespace(this) }
+
+    override string getName() { AST::namespaceName(this, result) }
+
+    override string toString() { result = "namespace " + this.getName() }
+  }
+
+  // Any syntax node that is a declaration
+  abstract class SourceDeclaration extends SourceElement {
+    abstract string getName();
+  }
+
+  // A syntax node that declares or defines a function
+  class SourceFunction extends SourceDeclaration {
+    SourceFunction() { AST::function(this) }
+
+    override string getName() { AST::functionName(this, result) }
+
+    override string toString() { result = this.getName() }
+
+    BlockStmt getBody() { AST::functionBody(this, result) }
+
+    SourceParameter getParameter(int i) { AST::functionParameter(this, i, result) }
+
+    SourceType getReturnType() { AST::functionReturn(this, result) }
+
+    predicate isDefinition() { AST::functionDefinition(this) }
+  }
+
+  // A syntax node that declares a variable (including fields and parameters)
+  class SourceVariableDeclaration extends SourceDeclaration {
+    SourceVariableDeclaration() { AST::variableDeclaration(this) }
+
+    override string getName() { AST::variableName(this, result) }
+
+    override string toString() { result = this.getName() }
+
+    SourceType getType() { AST::variableDeclarationType(this, result) }
+  }
+
+  // A syntax node that declares a parameter
+  class SourceParameter extends SourceVariableDeclaration {
+    SourceFunction fn;
+    int index;
+
+    SourceParameter() { AST::functionParameter(fn, index, this) }
+  }
+
+  class Stmt extends SourceElement {
+    Stmt() { AST::stmt(this) }
+
+    override string toString() { result = "stmt" }
+  }
+
+  class BlockStmt extends Stmt {
+    BlockStmt() { AST::blockStmt(this) }
+
+    override string toString() { result = "{ ... }" }
+  }
+
+  class Expr extends SourceElement {
+    Expr() { AST::expression(this) }
+  }
+
+  class AccessExpr extends Expr {
+    string identifier;
+
+    AccessExpr() { AST::accessExpr(this, identifier) }
+
+    string getName() { result = identifier }
+
+    override string toString() { result = this.getName() }
+  }
+
+  class CallExpr extends Expr {
+    CallExpr() { AST::callExpr(this) }
+
+    Expr getReceiver() { AST::callReceiver(this, result) }
+
+    Expr getArgument(int i) { AST::callArgument(this, i, result) }
+
+    override string toString() { result = "...(...)" }
+  }
+
+  class Literal extends Expr {
+    string value;
+
+    Literal() { AST::literal(this, value) }
+
+    override string toString() { result = value }
+
+    string getValue() { result = value }
+  }
+
+  class StringLiteral extends Literal {
+    StringLiteral() { AST::stringLiteral(this, _) }
+  }
+
+  abstract class SourceDefinition extends SourceDeclaration { }
+
+  class SourceTypeDefinition extends SourceDefinition {
+    SourceTypeDefinition() { AST::classOrStructDefinition(this) }
+
+    override string getName() { AST::typename(this, result) }
+
+    override string toString() { result = this.getName() }
+
+    SourceElement getAMember() { AST::classMember(this, _, result) }
+
+    predicate isDefinition() { AST::typeDefinition(this) }
+  }
+
+  // A node that contains a type of some kind
+  class SourceType extends SourceElement {
+    SourceType() { AST::type(this) }
+
+    override string toString() { AST::typename(this, result) }
+  }
+
+  class SourcePointer extends SourceType {
+    SourceType pointee;
+
+    SourcePointer() { AST::ptrType(this, pointee) }
+
+    SourceType getType() { result = pointee }
+  }
+
+  class SourceConst extends SourceType {
+    SourceType type;
+
+    SourceConst() { AST::constType(this, type) }
+
+    SourceType getType() { result = type }
+  }
+
+  class SourceReference extends SourceType {
+    SourceType type;
+
+    SourceReference() { AST::refType(this, type) }
+
+    SourceType getType() { result = type }
+  }
+}
+
+module TestAST = BuildlessAST<CompiledAST>;

cpp/ql/lib/experimental/buildless/checks.ql

@@ -0,0 +1,3 @@
+import Model
+
+select 1

cpp/ql/lib/experimental/buildless/identifiers.qll

@@ -0,0 +1,31 @@
+import ast_sig
+import ast
+import compiled_ast // For debugging in context
+
+module BuildlessIdentifiers<BuildlessASTSig A> {
+  module AST = Buildless<A>;
+
+  string getQualifiedName(AST::SourceNamespace ns) {
+    not exists(AST::SourceNamespace p | ns = p.getAChild()) and result = ns.getName()
+    or
+    exists(AST::SourceNamespace p | ns = p.getAChild() and ns !=p|
+      result = getQualifiedName(p) + "::" + ns.getName()
+    )
+  }
+
+  predicate namespace(string ns) {
+    ns = ["", getQualifiedName(_)]
+  }
+
+  // What are the identifiers in scope at a given point in the program?
+  // Give a potential object that the identifier refers to
+  AST::SourceDeclaration nameLookup(AST::SourceScope scope) {
+    result = scope
+    or
+    result = scope.(AST::SourceNamespace).getAChild()
+    or
+    result = scope.(AST::SourceTypeDefinition).getAMember()
+  }
+}
+
+module TestIdentifiers = BuildlessIdentifiers<CompiledAST>;

cpp/ql/lib/experimental/buildless/test_ast.ql

@@ -0,0 +1,26 @@
+import AST
+import types
+
+query TestAST::SourceFunction lua_copy() { result.getName() = "lua_copy" }
+
+query int lua_copy_count() { result = count(lua_copy()) }
+
+query predicate variables(TestAST::SourceVariableDeclaration decl, TestAST::SourceType sourceType) {
+  sourceType = decl.getType()
+}
+
+query predicate naiveCallTargets(TestAST::CallExpr call, TestAST::SourceFunction target) {
+  call.getReceiver().(TestAST::AccessExpr).getName() = target.getName() and
+  target.getName() = "max"
+}
+
+query predicate fnParents(TestAST::SourceFunction fn, TestAST::SourceNamespace parent) {
+  parent = fn.getParent()
+}
+
+query predicate includes(TestAST::Include include, File target) { target = include.getATarget() }
+
+query predicate unresolvedIncludes(TestAST::Include include) { not exists(include.getATarget()) }
+
+from TestAST::SourceFunction fn
+select fn, fn.getReturnType(), count(fn.getReturnType()), fn.getReturnType().getAQlClass()

cpp/ql/lib/experimental/buildless/test_model.ql

@@ -0,0 +1,13 @@
+import Model
+
+query predicate multipleDefinitions(TestModel::Type type, TestModel::SourceTypeDefinition def1, TestModel::SourceTypeDefinition def2)
+{
+    def1 = type.getADefinition() and
+    def2 = type.getADefinition() and 
+    def1.getLocation() != def2.getLocation() and
+    def1 != def2
+}
+
+from TestModel::SourceDeclaration decl
+where decl.getParent+()=decl
+select decl, "This has an invalid parent $@", decl.getParent()

cpp/ql/lib/experimental/buildless/test_types.ql

@@ -0,0 +1,34 @@
+import types
+
+query predicate constPointers(TestAST::SourceType t, TestAST::SourceConst c, TestAST::SourcePointer p)
+{
+    p.getType() = c and 
+    t = c.getType()
+}
+
+query predicate constRefs(TestAST::SourceType t, TestAST::SourceConst c, TestAST::SourceReference p)
+{
+    p.getType() = c and 
+    t = c.getType()
+}
+
+query predicate nestedNamespaces(TestAST::SourceNamespace parent, TestAST::SourceNamespace child)
+{
+    child = parent.getAChild()
+}
+
+query predicate recursiveNamespace(TestAST::SourceNamespace ns, TestAST::SourceNamespace descendents)
+{
+    ns = ns.getAChild+() and
+    descendents = ns.getAChild+()
+}
+
+query predicate usertypes(TestAST::SourceNamespace ns, TestAST::SourceTypeDefinition td)
+{
+    td = ns.getAChild()
+}
+
+// Let's try to resolve the type of a local variable
+
+from TestTypes::Type t
+select t

cpp/ql/lib/experimental/buildless/types.qll

@@ -0,0 +1,34 @@
+import AST
+
+module BuildlessTypes<BuildlessASTSig Sig> {
+  module AST = BuildlessAST<Sig>;
+
+  private newtype TType =
+    TBuiltinType(string name) { name = ["int", "char"] }
+    or
+    TUserType(string fqn) { exists(AST::SourceTypeDefinition d | d.getName() = fqn) }
+    //or
+    //TPointerType(Type type) { exists(A::SourcePointer p | p.getType() = type) }
+    //or
+    //TConstType(Type type) { exists(A::SourceConst c | c.getType() = type) }
+
+  class Type extends TType {
+    string toString() { result = this.getName() }
+
+    abstract string getName();
+    Location getLocation() { none() }
+  }
+
+  class BuiltinType extends Type, TBuiltinType {
+    override string getName() { this = TBuiltinType(result) }
+  }
+
+  class UserType extends Type, TUserType
+  {
+    override string getName() { this = TUserType(result) }
+
+    override Location getLocation() { exists(AST::SourceTypeDefinition d | this.getName() = d.getName() | result = d.getLocation()) }
+  }
+}
+
+module TestTypes = BuildlessTypes<CompiledAST>;