github / github/codeql

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

Abierto
#11,685 1 comentario 0 reacciones 0 asignados Ver en GitHub
question
Lenguaje dominante
CodeQL
Estrellas
10.1k
Forks
2.1k
Merge medio
2 d 15 h
PR fusionados (30 d)
141

Descripción

**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.

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.