github / github/codeql

[bug] codeql duplicates some graph nodes in bqrs while generating cpp AST using a kind=graph query

Ouverte
#11,685 1 commentaire 0 réactions 0 personnes assignées Voir sur GitHub
question
Langage dominant
CodeQL
Étoiles
10.1k
Forks
2.1k
Merge moyen
2 j 15 h
PR mergées (30 j)
141

Description

**Bugs in generating AST for cpp**

For research pusposes, I need the codeql's ability of generating ASTs of specific functions in C/C++, which are further parsed and used.

Occasionally, I encounterd weird cases where generated ASTs are empty or wrong. Here is a failed one.

## environment

codeql-cli 2.11.1, Linux x64

## reproduction

```bash
$ cat /func.ql
/**
* @name Print targeted AST
* @description Outputs a representation of a file's Abstract Syntax Tree.
* @id cpp/diff-ast
* @kind graph
* @tags print-diff-ast
*/

import cpp
import semmle.code.cpp.PrintAST
import definitions

class Cfg extends PrintAstConfiguration {
override predicate shouldPrintFunction(Function func) {
func.hasEntryPoint() and
(func.getName() in ["build_model"])
}
}
```

```bash
git clone https://github.com/libexpat/libexpat.git
cd libexpat && git reset --hard 9b4ce651b26557f16103c3a366c91934ecd439ab
cd expat && mkdir build && cd build && cmake ..
codeql database create -l cpp -j 8 -- libexpat
codeql database analyze --format=graphtext --output=ast --rerun -- libexpat /func.ql
```

With this, I got a resulting AST in graphtext form which looks like:

```bash
$ cat ast/cpp/diff-ast.txt
libexpat/expat/lib/xmlparse.c:
# 7321| [Parameter] parser
# 7321| Type = [CTypedefType] XML_Parser

# 7326| [DeclStmt] declaration
#-----| getDeclarationEntry(0) -> [VariableDeclarationEntry] definition of dtd

# 7326| [VariableAccess] parser
# 7326| Type = [CTypedefType] XML_Parser
# 7326| ValueCategory = prvalue(load)

# 7326| [PointerFieldAccess] m_dtd
# 7326| Type = [PointerType] DTD *
# 7326| ValueCategory = prvalue(load)
#-----| getQualifier() -> [VariableAccess] parser

# 7326| [Initializer] initializer for dtd
#-----| getExpr() -> [PointerFieldAccess] m_dtd

# 7327| [DeclStmt] declaration
#-----| getDeclarationEntry(0) -> [VariableDeclarationEntry] definition of ret
#-----| getDeclarationEntry(0) -> [VariableDeclarationEntry] definition of ret

# 7328| [DeclStmt] declaration
#-----| getDeclarationEntry(0) -> [VariableDeclarationEntry] definition of str

# 7342| [IfStmt] if (...) ...
#-----| getCondition() -> [GTExpr] ... > ...
#-----| getThen() -> [BlockStmt] { ... }

# 7342| [VariableAccess] dtd
# 7342| Type = [PointerType] DTD *
# 7342| ValueCategory = prvalue(load)

# 7342| [PointerFieldAccess] scaffCount
# 7342| Type = [IntType] unsigned int
# 7342| ValueCategory = prvalue(load)
#-----| getQualifier() -> [VariableAccess] dtd
...
```

This is surely a total mess, not in tree form. Analyzing the log i got this piece at the end:

```bash
$ tail libexpat/log/database-analyze-20221214.092131.537.log
[2022-12-14 09:21:36] [DETAILS] database interpret-results> Interpreted graph query "Print targeted AST" (cpp/diff-ast) at path /home/fullway/project/patch2ql/ql/cpp/ql/src/custom/DiffAST3.ql.
[2022-12-14 09:21:36] [WARN] Graph is not a valid forest. Node 67 has multiple predecessors
[2022-12-14 09:21:36] Plumbing command codeql database interpret-results completed.
[2022-12-14 09:21:36] Terminating normally.
```

It reminds me that a node in the bqrs has multiple predecessors. Locating the node 67 in the raw bqrs I got:

```bash
$ codeql bqrs decode --entities=all --
Result set: edges
| ID of source | source | URL for source | ID of target | target | URL for target | key | value |
...
| 269 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | 67 | [Initializer] initializer for dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:22:7383:25 | semmle.order | 1 |
| 269 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | 67 | [Initializer] initializer for dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:22:7383:25 | semmle.label | getVariable().getInitializer() |
| 270 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | 67 | [Initializer] initializer for dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:22:7383:25 | semmle.order | 1 |
| 270 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | 67 | [Initializer] initializer for dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:22:7383:25 | semmle.label | getVariable().getInitializer() |
...

Result set: nodes
| ID of node | node | URL for node | key | value |
...
| 269 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | semmle.label | [VariableDeclarationEntry] definition of dest |
| 269 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | Type | [PointerType] XML_Content * |
| 270 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | semmle.label | [VariableDeclarationEntry] definition of dest |
| 270 | [VariableDeclarationEntry] definition of dest | file:///data2/fullway/exp/libexpat/expat/lib/xmlparse.c:7383:16:7383:19 | Type | [PointerType] XML_Content * |
...
```

It did splits 2 separate nodes, 269 and 270, for one VariableDeclarationEntry, hence 2 predecessor edges for the initializer node and a cycle in the output graph.

Guide de contribution

Ouvrir le guide de contribution

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.