Skip to contentSkip to conversation

parsing of C code

Cocci Julia Lawall 3 participants 17 messages Aug 22, 2017 – Aug 24, 2017

lore
Share & tools
lore
#0 lore raw

Hello,

I have tried to improve the parsing of C code recently. The main changes, currently available on github, are as follows:

1. More aggressive inclusion of header files, combined with caching of header files. Now if there is only one occurrence of a header file with a given name in the provided include paths, it will take that one, even if there is no obvious connection between the location of the .c file and the location of the header file. This compensates for the lact of parsing of Makefiles to extract -I options. More header files will likely now be included, particularly with options like --all-includes or --recursive-includes. But caching of previously parsed header files has been reinstated, which improves performance. This had been removed because it wasn't doing nested includes, even if the --recursive-includes option was provided, but that issue has been addressed.

2. If there is a parse error within the arguments of a function call, the arguments are ignored, but not the entire enclosing functions definition, as was done previously. For the Linux kernel, this seemed to allow thousands of extra lines of code to be parsed and matched by Coccinelle.

I have only tested this on the Linux kernel. If you are using some other software, you can run the following semantic patch on your software using your current and the new versions of Coccinelle:

@r@
identifier f;
position p;
@@

f at p(...) { ... }

@script:ocaml@
f << r.f;
p << r.p;
@@

Printf.printf "%s:%d: %s\n" (List.hd p).file (List.hd p).line f; flush stdout

If some functions are missing in the output when using the new version, as compared to the output when using the old version, and if these functions are things you might want to process in some way, thenlet me know about the problem.

thanks,
julia

#1 lore raw

Julia,

Quoted 2 lines

1. More aggressive inclusion of header files, combined with caching of header files. Now if there is only one occurrence of a header file with a

Caching can be dangerous because macros may be defined differently for different includes of the same header. An option to switch off caching could come in handy.

Quoted 4 lines

given name in the provided include paths, it will take that one, even if there is no obvious connection between the location of the .c file and the location of the header file. This compensates for the lact of parsing of Makefiles to extract -I options. More header files will likely now be

There is no need to parse Makefiles. Simply create a script, say coc99, and configure it as the compiler that make uses. coc99 parses its arguments to extract whatever information cocci needs and passes everything to the 'real' C compiler as-is.

How is the O'Reilly book coming along ;-)

Signature · 2 lines
Derek M. Jones           Software analysis
tel: +44 (0)1252 520667  blog:shape-of-code.coding-guidelines.com
#2 lore raw
Quoted 8 lines · Derek M Jones

Julia,

Quoted 2 lines

1. More aggressive inclusion of header files, combined with caching of header files. Now if there is only one occurrence of a header file with a

Caching can be dangerous because macros may be defined differently for different includes of the same header. An option to switch off caching could come in handy.

I believe that macros are only applied if they are defined in the same file. At this point, I'm not 100% certain of that. But when I ran the provided test script on the Linux kernel, I list very few functions as compared to the current --recursive-includes implementation. The lost functions were due to the recovery strategy, not to macro issues. The Linux kernel has some declarations like

type fn(a1, a2)

with no trailing ; followed by a function definition. This gives a parse error on a1. In the previous version, Coccinelle was able to recover an parse the function definition. In the new version, I comment out the arguments and then another error is encountered that is after the ). This causes the recovery process to skip over the subsequent function. The recovery code is rather subtle to avoid infinite loops, and so far my attempts to improve it have led to more of a mess than anything else.

The problem could be solved by not trying to patch up errors in parentheses when they occur at top level. When they occur inside a function, they should not impact the recovery process.

Basically the recovery process is focused on finding a { in column 0 and then a } in column 0, and then it goes on after that. But it can go backwards sometimes, because a parsing problem can cause a parsing attempt to read too far, into the next function.

Quoted 10 lines
Quoted 5 lines

given name in the provided include paths, it will take that one, even if there is no obvious connection between the location of the .c file and the location of the header file. This compensates for the lact of parsing of Makefiles to extract -I options. More header files will likely now be

There is no need to parse Makefiles. Simply create a script, say coc99, and configure it as the compiler that make uses. coc99 parses its arguments to extract whatever information cocci needs and passes everything to the 'real' C compiler as-is.

At least for the Linux kernel, you can't just run one make and get all the files to be compiled. Some files are indeed very hard to compile. For a more uniform project this could work, though.

Quoted 1 line

How is the O'Reilly book coming along ;-)

Still looking for an author :)

julia

Quoted 9 lines

--
Derek M. Jones Software analysis
tel: +44 (0)1252 520667 blog:shape-of-code.coding-guidelines.com
_______________________________________________
Cocci mailing list
Cocci at systeme.lip6.fr
https://systeme.lip6.fr/mailman/listinfo/cocci

#3 lore raw

Julia,

Quoted 5 lines

The Linux kernel has some declarations like

type fn(a1, a2) >
with no trailing ; followed by a function definition. This gives a parse error on a1. In the previous version, Coccinelle was able to recover an

The K&R style. Perfectly legal C.

Quoted 4 lines

Basically the recovery process is focused on finding a { in column 0 and then a } in column 0, and then it goes on after that. But it can go backwards sometimes, because a parsing problem can cause a parsing attempt to read too far, into the next function.

Skip to ; is a remarkably effective syntax error recovery strategy.

Signature · 2 lines
Derek M. Jones           Software analysis
tel: +44 (0)1252 520667  blog:shape-of-code.coding-guidelines.com
#4 lore raw
Quoted 9 lines · Derek M Jones

Julia,

Quoted 5 lines

The Linux kernel has some declarations like

type fn(a1, a2) >
with no trailing ; followed by a function definition. This gives a parse error on a1. In the previous version, Coccinelle was able to recover an

The K&R style. Perfectly legal C.

I don't think that is what it is. The declarations are eg:

static inline __printf(2, 3)
void _dev_info(const struct device *dev, const char *fmt, ...) {}

I guess that the whole first line is part of the declaration of _dev_info, but Coccinelle can't cope with the __printf(2, 3).

Quoted 7 lines
Quoted 5 lines

Basically the recovery process is focused on finding a { in column 0 and then a } in column 0, and then it goes on after that. But it can go backwards sometimes, because a parsing problem can cause a parsing attempt to read too far, into the next function.

Skip to ; is a remarkably effective syntax error recovery strategy.

The parser needs to restart at a top-level declaration. It's a yacc-based parser. We can't recover within the parsing process. Perhaps it would be possible to remove what was betwen two ;s around the line and column with the error, but it seems like there could be a risk of making things worse.

julia

Quoted 6 lines

--
Derek M. Jones Software analysis
tel: +44 (0)1252 520667 blog:shape-of-code.coding-guidelines.com

#5 lore raw

Julia,

Quoted 8 lines

I don't think that is what it is. The declarations are eg:

static inline __printf(2, 3)
void _dev_info(const struct device *dev, const char *fmt, ...) {}

I guess that the whole first line is part of the declaration of _dev_info, but Coccinelle can't cope with the __printf(2, 3).

https://stackoverflow.com/questions/17825588/what-does-this-generic-function-do

Quoted 6 lines
Quoted 1 line

Skip to ; is a remarkably effective syntax error recovery strategy.

The parser needs to restart at a top-level declaration. It's a yacc-based parser. We can't recover within the parsing process. Perhaps it would be possible to remove what was betwen two ;s around the line and column with the error, but it seems like there could be a risk of making things worse.

If it's yacc based you can recover where ever you like. Knowing how to do it is something of a black art.

Bison supports a technique that does not require wearing a pointy hat:

stmt_list: error ';' |

            stmt_list error ';' ;

where error represents the something-went-wrong token.

Signature · 2 lines
Derek M. Jones           Software analysis
tel: +44 (0)1252 520667  blog:shape-of-code.coding-guidelines.com
#6 lore raw
Quoted 15 lines · Derek M Jones

Julia,

Quoted 8 lines

I don't think that is what it is. The declarations are eg:

static inline __printf(2, 3)
void _dev_info(const struct device *dev, const char *fmt, ...) {}

I guess that the whole first line is part of the declaration of _dev_info, but Coccinelle can't cope with the __printf(2, 3).

https://stackoverflow.com/questions/17825588/what-does-this-generic-function-do

Quoted 2 lines
Quoted 1 line

Skip to ; is a remarkably effective syntax error recovery strategy.

Quoted 7 lines
Quoted 4 lines

The parser needs to restart at a top-level declaration. It's a yacc-based parser. We can't recover within the parsing process. Perhaps it would be possible to remove what was betwen two ;s around the line and column with the error, but it seems like there could be a risk of making things worse.

If it's yacc based you can recover where ever you like. Knowing how to do it is something of a black art.

Well, ocamlyacc, to be precise.

Quoted 7 lines

Bison supports a technique that does not require wearing a pointy hat:

stmt_list: error ';' |

           stmt_list error ';' ;

where error represents the something-went-wrong token.

This does look like a nice feature.

julia

#7 lore raw
Quoted 4 lines
Quoted 2 lines

If it's yacc based you can recover where ever you like. Knowing how to do it is something of a black art.

Well, ocamlyacc, to be precise.

Can the software ?Menhir? help any more for the needed data processing?
http://gallium.inria.fr/%7Efpottier/menhir/

Regards,
Markus

#8 lore raw
In reply to Julia Lawall
Quoted 2 lines

At least for the Linux kernel, you can't just run one make and get all the files to be compiled. Some files are indeed very hard to compile.

How do you think about to point any specific source code examples out which you find a bit too challenging so far?

Regards,
Markus

#9 lore raw
In reply to Derek M Jones
Quoted 8 lines · Derek M Jones

Julia,

Quoted 2 lines

1. More aggressive inclusion of header files, combined with caching of header files. Now if there is only one occurrence of a header file with a

Caching can be dangerous because macros may be defined differently for different includes of the same header. An option to switch off caching could come in handy.

I can add such an option.

Actually, I noticed that unfolding macros can sometimes hurt more than it helps. When Coccinelle decides to unfold macros it unfolds them for all the rest of the code, but it only unfolds one level of macro. Sometimes the one-level unfolding is weirder than the original and the parser error that triggered unfoding is not related to macros anyway. So then the whole rest of the code has a weird semi-unfolded macro in it for no purpose, whe it could have compiled normally. At least for the Linux kernel, though, this seems like a rare occurrence.

julia

#10 lore raw
Quoted 1 line

Actually, I noticed that unfolding macros can sometimes hurt more than it helps.

Would you like to discuss (or explain) involved implementation details and configuration parameters any more?

Regards,
Markus

#11 lore raw
Quoted 4 lines · SF Markus Elfring
Quoted 1 line

Actually, I noticed that unfolding macros can sometimes hurt more than it helps.

Would you like to discuss (or explain) involved implementation details and configuration parameters any more?

#define FOO(x) BAR(x,+,y)

int foo() __xxx(yyy) {
FOO(12);
}

int xyz() {
FOO(15);
}

Parsing of foo fails due to the attribute __xxx(yyy) that Coccinelle is not able to cope with. Coccinele hopes that expanding macros will solve the problem. Now the code becomes:

#define FOO(x) BAR(x,+,y)

int foo() __xxx(yyy) {
BAR(12,+,y);
}

int xyz() {
BAR(15,+,y);
}

Now foo is still unparsable, but xyz is unparsable as well. It would have been better off with FOO(15);

julia

#12 lore raw
Quoted 2 lines

Parsing of foo fails due to the attribute __xxx(yyy) that Coccinelle is not able to cope with.

Why does the parsing software struggle with such input data so far?

Quoted 1 line

Coccinele hopes that expanding macros will solve the problem.

Why do you need to ?hope? something if the software could be designed in the way to take also special care with these source code places?

Do you eventually stumble on target conflicts because of language processing difficulties which could be explained from the Chomsky?Sch?tzenberger hierarchy?

Regards,
Markus

#13 lore raw
In reply to Julia Lawall
Quoted 2 lines

Parsing of foo fails due to the attribute __xxx(yyy) that Coccinelle is not able to cope with.

* Do you find information relevant from answers to a question like ?Context-free grammars versus context-sensitive grammars???
https://stackoverflow.com/questions/8236422/context-free-grammars-versus-context-sensitive-grammars#answer-8250104

* Do the ?attributes? which you would like to support trigger a need to work with context-dependent grammars?

* Did you ask any other developers (or software designers) for possible solutions around the mentioned aspect?

* Will the software situation improve any more also for the programming language ?OCaml? (besides tools like ?Menhir?)?

Regards,
Markus

#14 lore raw

On 24/08/2017 16:23, SF Markus Elfring wrote:

More importantly; does Julia like red jelly beans more than blue jelly beans?

Quoted 16 lines

* Do you find information relevant from answers to a question like ?Context-free grammars versus context-sensitive grammars???
https://stackoverflow.com/questions/8236422/context-free-grammars-versus-context-sensitive-grammars#answer-8250104

* Do the ?attributes? which you would like to support trigger a need to work with context-dependent grammars?

* Did you ask any other developers (or software designers) for possible solutions around the mentioned aspect?

* Will the software situation improve any more also for the programming language ?OCaml? (besides tools like ?Menhir?)?

Regards,
Markus

Signature · 2 lines
Derek M. Jones           Software analysis
tel: +44 (0)1252 520667  blog:shape-of-code.coding-guidelines.com
#15 lore raw
Quoted 1 line

More importantly; does Julia like red jelly beans more than blue jelly beans?

Would you like to discuss favourite sweets more than to clarify further improvements in parsing technology also for application
together with the Coccinelle software? ;-)

Regards,
Markus

#16 lore raw
In reply to Julia Lawall
Quoted 1 line

I have tried to improve the parsing of C code recently.

This information is useful.

Quoted 1 line

1. More aggressive inclusion of header files,

Why do you need to become ?aggressive? there when the corresponding data processing should be just correct?

Quoted 1 line

combined with caching of header files.

How do you think about to configure this approach with special parameters?

Quoted 1 line

flush stdout

Can such a function call be omitted here?

Quoted 4 lines

If some functions are missing in the output when using the new version, as compared to the output when using the old version, and if these functions are things you might want to process in some way, thenlet me know about the problem.

I became more curious on the run time characteristics (as you already know) for the presented software evolution. I stumbled on some execution challenges during the application of special source code search patterns. How would they increase because of the desired inclusion of additional source (or header) files for analysis approaches which would need them?

Regards,
Markus