Add support for kconfig constraints
cover Add support for kconfig constraints
This patchset adds a support for generic boolean expressions in order to be able to check for a more complex kernel configurations.
The motivation for this is recent rename in kernel config names that cannot be checked for by a simplistic approach we previously implemented.
The boolean expression parser was written as a generic as possible since I do expect that we will reuse it for different types of assertions in the future.
Cyril Hrubis (3):
lib/tst_kconfig: Rewrite the parser internals
lib: Add generic boolean expression parser and eval lib/tst_kconfig: Make use of boolean expression eval
doc/test-writing-guidelines.txt | 21 +- include/tst_bool_expr.h | 80 +++++ include/tst_kconfig.h | 34 ++- lib/newlib_tests/.gitignore | 1 + lib/newlib_tests/test_kconfig.c | 1 + lib/newlib_tests/tst_bool_expr.c | 127 ++++++++ lib/tst_bool_expr.c | 504 +++++++++++++++++++++++++++++++ lib/tst_kconfig.c | 310 ++++++++++++------- 8 files changed, 939 insertions(+), 139 deletions(-) create mode 100644 include/tst_bool_expr.h create mode 100644 lib/newlib_tests/tst_bool_expr.c create mode 100644 lib/tst_bool_expr.c
Signature · 1 line
2.26.2
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
This patch changes the parser internals so that the parser results are not tied to the kconfigs array from the tst_test structure anymore.
This is a first step to a parser that can parse more complex expressions.
--- include/tst_kconfig.h | 34 ++++---- lib/tst_kconfig.c | 184 +++++++++++++++++++----------------------- 2 files changed, 103 insertions(+), 115 deletions(-)
include/tst_kconfig.h +18 -16
@@ -6,27 +6,27 @@#ifndef TST_KCONFIG_H__ #define TST_KCONFIG_H__ -struct tst_kconfig_res { -char match; -char *value; +struct tst_kconfig_var { +char id[64 ]; +unsigned int id_len; +char choice; +char *val; };/** -* Reads a kernel config and parses it for values defined in kconfigs array. +* +* Reads a kernel config, parses it and writes results into an array of +* tst_kconfig_var structures. * * The path to the kernel config should be autodetected in most of the cases as * the code looks for know locations. It can be explicitely set/overrided with * the KCONFIG_PATH environment variable as well. * -* The kcofings array is expected to contain strings in a format "CONFIG_FOO" -* or "CONFIG_FOO=bar". The result array has to be suitably sized to fit the -* results. -* -* @param kconfigs array of config strings to look for -* @param results array to store results to -* @param cnt size of the arrays +* The caller has to initialize the tst_kconfig_var structure. The id has to be +* filled with config variable name such as 'CONFIG_FOO', the id_len should +* hold the id string length and the choice and val has to be zeroed. * -* The match in the tst_kconfig_res structure is set as follows: +* After a call to this function each choice be set as follows: * * 'm' - config option set to m * 'y' - config option set to y
@@ -34,11 +34,13 @@ struct tst_kconfig_res {* 'n' - config option is not set * 0 - config option not found * -* In the case that match is set to 'v' the value points to a newly allocated -* string that holds the value. +* In the case that match is set to 'v' the val pointer points to a newly +* allocated string that holds the value. +* +* @param vars An array of caller initalized tst_kconfig_var structures. +* @param vars_len Length of the vars array. */ -void tst_kconfig_read (const char *const kconfigs[], -struct tst_kconfig_res results[],size_t cnt); +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len);/** * Checks if required kernel configuration options are set in the kernel
lib/tst_kconfig.c +85 -99
259 lines not on this page · raw message
Signature · 1 line
2.26.2
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hello,
Quoted 17 lines · Cyril Hrubis
This patch changes the parser internals so that the parser results are not tied to the kconfigs array from the
tst_teststructure anymore.This is a first step to a parser that can parse more complex expressions.
Signed-off-by Cyril Hrubis <[email protected]>--- include/tst_kconfig.h | 34 ++++---- lib/tst_kconfig.c | 184 +++++++++++++++++++----------------------- 2 files changed, 103 insertions(+), 115 deletions(-)include/tst_kconfig.h +0
-0
include/tst_kconfig.h line 12
Quoted 10 lines
include/tst_kconfig.h +4
-3@@ -6,27 +6,27 @@ #ifndef TST_KCONFIG_H__ #define TST_KCONFIG_H__ -struct tst_kconfig_res { - char match; - char *value; +struct tst_kconfig_var { + char id[64]; + unsigned int id_len; + char choice;
This should probably be an enum to give the compiler more info. Even if we use the current char values as the enum entries.
Quoted 76 lines
include/tst_kconfig.h +14
-13+char *val; };/** -* Reads a kernel config and parses it for values defined in kconfigs array. +* +* Reads a kernel config, parses it and writes results into an array of +* tst_kconfig_var structures. * * The path to the kernel config should be autodetected in most of the cases as * the code looks for know locations. It can be explicitely set/overrided with * the KCONFIG_PATH environment variable as well. * -* The kcofings array is expected to contain strings in a format "CONFIG_FOO" -* or "CONFIG_FOO=bar". The result array has to be suitably sized to fit the -* results. -* -* @param kconfigs array of config strings to look for -* @param results array to store results to -* @param cnt size of the arrays +* The caller has to initialize the tst_kconfig_var structure. The id has to be +* filled with config variable name such as 'CONFIG_FOO', the id_len should +* hold the id string length and the choice and val has to be zeroed. * -* The match in the tst_kconfig_res structure is set as follows: +* After a call to this function each choice be set as follows: * * 'm' - config option set to m * 'y' - config option set to y @@ -34,11 +34,13 @@ struct tst_kconfig_res {* 'n' - config option is not set * 0 - config option not found * -* In the case that match is set to 'v' the value points to a newly allocated -* string that holds the value. +* In the case that match is set to 'v' the val pointer points to a newly +* allocated string that holds the value. +* +* @param vars An array of caller initalized tst_kconfig_var structures. +* @param vars_len Length of the vars array. */ -void tst_kconfig_read (const char *const kconfigs[], -struct tst_kconfig_res results[],size_t cnt); +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len);/** * Checks if required kernel configuration options are set in the kernel lib/tst_kconfig.c +3
-11@@ -84,15 +84,6 @@ static void close_kconfig(FILE *fp)fclose (fp); } -struct match { -/* match len, string length up to \0 or = */ -size_t len; -/* if set part of conf string after = */ -const char *val; -/* if set the config option was matched already */ -int match; -}; -static int is_set (const char *str,const char *val) {size_t vlen =strlen (val);@@ -114,96 +105,70 @@ static int is_set(const char *str, const char *val) } } -static inline int match (struct match *match,const char *conf, -struct tst_kconfig_res *result,const char *line) +static inline int kconfig_parse_line (const char *line, +struct tst_kconfig_var *vars, +unsigned int vars_len)
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 117
Quoted 10 lines
lib/tst_kconfig.c +5
-3{ -if (match->match) -return 0 ; +unsigned int i; -const char *cfg =strstr (line,"CONFIG_" ); +for (i =0 ; i < vars_len; i++) { +if (!strncmp (vars[i].id, line, vars[i].id_len)) { +const char *val = &line[vars[i].id_len]; +
It is valid to have 'CONFIG_VAR = y'. We should probably tokenize the lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 125
Quoted 8 lines
lib/tst_kconfig.c +8
-0+switch (val[0 ]) { +case '=' : +break ; +case ' ' : +if (is_set (val,"is not set" )) { + vars[i].choice ='n' ; +return 1 ; + }
Typically such lines begin with a comment '#' and I don't see where that is handled. Possibly this will only match non standard configs?
Quoted 97 lines
lib/tst_kconfig.c +21
-62+return 1 ; +/* vars[i].id may be prefix to longer config var */ +default : +return 0 ; + } -if (!cfg) -return 0 ; +if (is_set (val,"=y" )) { + vars[i].choice ='y' ; +return 1 ; + } -if (strncmp (cfg, conf, match->len)) -return 0 ; +if (is_set (val,"=m" )) { + vars[i].choice ='m' ; +return 1 ; + } -const char *val = &cfg[match->len]; + vars[i].choice ='v' ; + vars[i].val =strndup (val+1 ,strlen (val)-2 ); -switch (cfg[match->len]) { -case '=' : -break ; -case ' ' : -if (is_set (val,"is not set" )) { - result->match ='n' ; - goto match; +return 1 ; } -/* fall through */ -default : -return 0 ; - } - -if (is_set (val,"=y" )) { - result->match ='y' ; - goto match; } -if (is_set (val,"=m" )) { - result->match ='m' ; - goto match; - } - - result->match ='v' ; - result->value =strndup (val+1 ,strlen (val)-2 ); - -match: - match->match =1 ; -return 1 ; +return 0 ; } -void tst_kconfig_read (const char *const *kconfigs, -struct tst_kconfig_res results[],size_t cnt) +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len) { -struct match matches[cnt]; -FILE *fp; -unsigned int i, j; -char buf[1024 ]; - -for (i =0 ; i < cnt; i++) { -const char *val =strchr (kconfigs[i],'=' ); - -if (strncmp ("CONFIG_" , kconfigs[i],7 )) -tst_brk (TBROK ,"Invalid config string '%s'" , kconfigs[i]); +char line[128 ]; +unsigned int vars_found =0 ; - matches[i].match =0 ; - matches[i].len =strlen (kconfigs[i]); - -if (val) { - matches[i].val = val +1 ; - matches[i].len -=strlen (val); - } - - results[i].match =0 ; - results[i].value =NULL ; - } - - fp =open_kconfig (); +FILE *fp =open_kconfig ();if (!fp)tst_brk (TBROK ,"Cannot parse kernel .config" ); -while (fgets (buf,sizeof (buf), fp)) { -for (i =0 ; i < cnt; i++) { -if (match (&matches[i], kconfigs[i], &results[i], buf)) { -for (j =0 ; j < cnt; j++) { -if (matches[j].match) -break ;
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 165
Quoted 10 lines
lib/tst_kconfig.c +4
-5- } +while (fgets (line,sizeof (line), fp)) { +char *cfg =strstr (line,"CONFIG_" ); -if (j == cnt) - goto exit; - } - } +if (!cfg) +continue ;
This filtering seems unecessary and maybe will hide some corner cases because it reduces kconfig_parses_line's exposure. Also practically every line has 'CONFIG_' in it.
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 7 lines
lib/tst_kconfig.c +5
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++; +if (vars_found == vars_len) + goto exit; }
Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Quoted 108 lines
lib/tst_kconfig.c +39
-18exit:@@ -219,42 +184,63 @@ static size_t array_len(const char *const kconfigs[])return i; } -static int compare_res (struct tst_kconfig_res *res,const char *kconfig, -char match,const char *val) +static int compare_res (struct tst_kconfig_var *var,const char *kconfig, +char choice,const char *val) { -if (res->match != match) { -tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, res->match); +if (var->choice != choice) { +tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, var->choice);return 1 ; } -if (match !='v' ) +if (choice !='v' )return 0 ; -if (strcmp (res->value, val)) { -tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, res->value); +if (strcmp (var->val, val)) { +tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, var->val);return 1 ; }return 0 ; } +static inline unsigned int get_len (const char * kconfig) +{ +char *sep =index (kconfig,'=' ); + +if (!sep) +return strlen (kconfig); + +return sep - kconfig; +} +void tst_kconfig_check (const char *const kconfigs[]) { -size_t cnt =array_len (kconfigs); -struct tst_kconfig_res results[cnt]; +size_t vars_cnt =array_len (kconfigs); +struct tst_kconfig_var vars[vars_cnt];unsigned int i;int abort_test =0 ; -tst_kconfig_read (kconfigs, results, cnt); +memset (vars,0 ,sizeof (*vars) * vars_cnt); + +for (i =0 ; i < vars_cnt; i++) { + vars[i].id_len =get_len (kconfigs[i]); + +if (vars[i].id_len >=sizeof (vars[i].id)) +tst_brk (TBROK ,"kconfig var id too long!" ); + +strncpy (vars[i].id, kconfigs[i], vars[i].id_len); + } + +tst_kconfig_read (vars, vars_cnt); -for (i =0 ; i < cnt; i++) { -if (results[i].match ==0 ) { +for (i =0 ; i < vars_cnt; i++) { +if (vars[i].choice ==0 ) {tst_res (TINFO ,"Missing kernel %s" , kconfigs[i]); abort_test =1 ;continue ; } -if (results[i].match =='n' ) { +if (vars[i].choice =='n' ) {tst_res (TINFO ,"Kernel %s is not set" , kconfigs[i]); abort_test =1 ;continue ;@@ -263,21 +249,21 @@ void tst_kconfig_check(const char *const kconfigs[])const char *val =strchr (kconfigs[i],'=' );if (val) { -char match ='v' ; +char choice ='v' ; val++;if (!strcmp (val,"y" )) - match ='y' ; + choice ='y' ;if (!strcmp (val,"m" )) - match ='m' ; + choice ='m' ; -if (compare_res (&results[i], kconfigs[i], match, val)) +if (compare_res (&vars[i], kconfigs[i], choice, val)) abort_test =1 ; } -free (results[i].value); +free (vars[i].val); }if (abort_test)Signature · 1 line
2.26.2
I suppose most of the problems here stem from the original code, but your patch may as well clear it up :-)
Signature · 2 lines
Thank you, Richard.
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hi!
Quoted 8 lines
Quoted 8 lines
include/tst_kconfig.h +0
-0@@ -6,27 +6,27 @@#ifndef TST_KCONFIG_H__ #define TST_KCONFIG_H__
Quoted 10 lines
include/tst_kconfig.h line 12
Quoted 7 lines
include/tst_kconfig.h +4
-3-struct tst_kconfig_res { -char match; -char *value; +struct tst_kconfig_var { +char id[64 ]; +unsigned int id_len; +char choice;This should probably be an enum to give the compiler more info. Even if we use the current char values as the enum entries.
Actually I was thinking of getting rid of this entirely in a follow up patch and just keep the val, because after the last patch these values are not special anymore.
Quoted 81 lines
Quoted 81 lines
include/tst_kconfig.h +14
-13+char *val; };/** -* Reads a kernel config and parses it for values defined in kconfigs array. +* +* Reads a kernel config, parses it and writes results into an array of +* tst_kconfig_var structures. * * The path to the kernel config should be autodetected in most of the cases as * the code looks for know locations. It can be explicitely set/overrided with * the KCONFIG_PATH environment variable as well. * -* The kcofings array is expected to contain strings in a format "CONFIG_FOO" -* or "CONFIG_FOO=bar". The result array has to be suitably sized to fit the -* results. -* -* @param kconfigs array of config strings to look for -* @param results array to store results to -* @param cnt size of the arrays +* The caller has to initialize the tst_kconfig_var structure. The id has to be +* filled with config variable name such as 'CONFIG_FOO', the id_len should +* hold the id string length and the choice and val has to be zeroed. * -* The match in the tst_kconfig_res structure is set as follows: +* After a call to this function each choice be set as follows: * * 'm' - config option set to m * 'y' - config option set to y @@ -34,11 +34,13 @@ struct tst_kconfig_res {* 'n' - config option is not set * 0 - config option not found * -* In the case that match is set to 'v' the value points to a newly allocated -* string that holds the value. +* In the case that match is set to 'v' the val pointer points to a newly +* allocated string that holds the value. +* +* @param vars An array of caller initalized tst_kconfig_var structures. +* @param vars_len Length of the vars array. */ -void tst_kconfig_read (const char *const kconfigs[], -struct tst_kconfig_res results[],size_t cnt); +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len);/** * Checks if required kernel configuration options are set in the kernel lib/tst_kconfig.c +4
-13@@ -84,15 +84,6 @@ static void close_kconfig(FILE *fp)fclose (fp); } -struct match { -/* match len, string length up to \0 or = */ -size_t len; -/* if set part of conf string after = */ -const char *val; -/* if set the config option was matched already */ -int match; -}; -static int is_set (const char *str,const char *val) {size_t vlen =strlen (val);@@ -114,96 +105,70 @@ static int is_set(const char *str, const char *val) } } -static inline int match (struct match *match,const char *conf, -struct tst_kconfig_res *result,const char *line) +static inline int kconfig_parse_line (const char *line, +struct tst_kconfig_var *vars, +unsigned int vars_len) { -if (match->match) -return 0 ; +unsigned int i;
Quoted 10 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 117
Quoted 5 lines
lib/tst_kconfig.c +4
-1-const char *cfg =strstr (line,"CONFIG_" ); +for (i =0 ; i < vars_len; i++) { +if (!strncmp (vars[i].id, line, vars[i].id_len)) { +const char *val = &line[vars[i].id_len]; +It is valid to have '
CONFIG_VAR= y'. We should probably tokenize the lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
I guess that it's techincally possible to have a whitespaces there, but will not happen unless you hand-edit the config file before compilation, which I doubt will ever happen.
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 125
Quoted 8 lines
lib/tst_kconfig.c +8
-0+switch (val[0 ]) { +case '=' : +break ; +case ' ' : +if (is_set (val,"is not set" )) { + vars[i].choice ='n' ; +return 1 ; + }Typically such lines begin with a comment '#' and I don't see where that is handled. Possibly this will only match non standard configs?
It does work actually, since we use strstr() to get the "CONFIG_" prefix from each line of the configuration, but I guess this needs to be fixed anyways since we would detect "# CONFIG_FOO=y" as enabled config feature even if it's commented. Again this will not happen unless you hand-edit the file, but it's probably worth fixing in a follow up patch.
Quoted 101 lines
Quoted 101 lines
lib/tst_kconfig.c +23
-63+return 1 ; +/* vars[i].id may be prefix to longer config var */ +default : +return 0 ; + } -if (!cfg) -return 0 ; +if (is_set (val,"=y" )) { + vars[i].choice ='y' ; +return 1 ; + } -if (strncmp (cfg, conf, match->len)) -return 0 ; +if (is_set (val,"=m" )) { + vars[i].choice ='m' ; +return 1 ; + } -const char *val = &cfg[match->len]; + vars[i].choice ='v' ; + vars[i].val =strndup (val+1 ,strlen (val)-2 ); -switch (cfg[match->len]) { -case '=' : -break ; -case ' ' : -if (is_set (val,"is not set" )) { - result->match ='n' ; - goto match; +return 1 ; } -/* fall through */ -default : -return 0 ; - } - -if (is_set (val,"=y" )) { - result->match ='y' ; - goto match; } -if (is_set (val,"=m" )) { - result->match ='m' ; - goto match; - } - - result->match ='v' ; - result->value =strndup (val+1 ,strlen (val)-2 ); - -match: - match->match =1 ; -return 1 ; +return 0 ; } -void tst_kconfig_read (const char *const *kconfigs, -struct tst_kconfig_res results[],size_t cnt) +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len) { -struct match matches[cnt]; -FILE *fp; -unsigned int i, j; -char buf[1024 ]; - -for (i =0 ; i < cnt; i++) { -const char *val =strchr (kconfigs[i],'=' ); - -if (strncmp ("CONFIG_" , kconfigs[i],7 )) -tst_brk (TBROK ,"Invalid config string '%s'" , kconfigs[i]); +char line[128 ]; +unsigned int vars_found =0 ; - matches[i].match =0 ; - matches[i].len =strlen (kconfigs[i]); - -if (val) { - matches[i].val = val +1 ; - matches[i].len -=strlen (val); - } - - results[i].match =0 ; - results[i].value =NULL ; - } - - fp =open_kconfig (); +FILE *fp =open_kconfig ();if (!fp)tst_brk (TBROK ,"Cannot parse kernel .config" ); -while (fgets (buf,sizeof (buf), fp)) { -for (i =0 ; i < cnt; i++) { -if (match (&matches[i], kconfigs[i], &results[i], buf)) { -for (j =0 ; j < cnt; j++) { -if (matches[j].match) -break ; - } +while (fgets (line,sizeof (line), fp)) { +char *cfg =strstr (line,"CONFIG_" );
Quoted 10 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 165
Quoted 6 lines
lib/tst_kconfig.c +2
-4-if (j == cnt) - goto exit; - } - } +if (!cfg) +continue ;This filtering seems unecessary and maybe will hide some corner cases because it reduces kconfig_parses_line's exposure. Also practically every line has '
CONFIG_' in it.
Not really, there are empty lines and plenty of comments in the file generated by kernel infrastructure.
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 7 lines
lib/tst_kconfig.c +5
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++; +if (vars_found == vars_len) + goto exit; }Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Well we do expect well formatted .config file from a start, if you hand edit it and put whitespaces into unexpected places more things may fail.
Quoted 104 lines
Quoted 104 lines
lib/tst_kconfig.c +39
-18exit:@@ -219,42 +184,63 @@ static size_t array_len(const char *const kconfigs[])return i; } -static int compare_res (struct tst_kconfig_res *res,const char *kconfig, -char match,const char *val) +static int compare_res (struct tst_kconfig_var *var,const char *kconfig, +char choice,const char *val) { -if (res->match != match) { -tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, res->match); +if (var->choice != choice) { +tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, var->choice);return 1 ; } -if (match !='v' ) +if (choice !='v' )return 0 ; -if (strcmp (res->value, val)) { -tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, res->value); +if (strcmp (var->val, val)) { +tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, var->val);return 1 ; }return 0 ; } +static inline unsigned int get_len (const char * kconfig) +{ +char *sep =index (kconfig,'=' ); + +if (!sep) +return strlen (kconfig); + +return sep - kconfig; +} +void tst_kconfig_check (const char *const kconfigs[]) { -size_t cnt =array_len (kconfigs); -struct tst_kconfig_res results[cnt]; +size_t vars_cnt =array_len (kconfigs); +struct tst_kconfig_var vars[vars_cnt];unsigned int i;int abort_test =0 ; -tst_kconfig_read (kconfigs, results, cnt); +memset (vars,0 ,sizeof (*vars) * vars_cnt); + +for (i =0 ; i < vars_cnt; i++) { + vars[i].id_len =get_len (kconfigs[i]); + +if (vars[i].id_len >=sizeof (vars[i].id)) +tst_brk (TBROK ,"kconfig var id too long!" ); + +strncpy (vars[i].id, kconfigs[i], vars[i].id_len); + } + +tst_kconfig_read (vars, vars_cnt); -for (i =0 ; i < cnt; i++) { -if (results[i].match ==0 ) { +for (i =0 ; i < vars_cnt; i++) { +if (vars[i].choice ==0 ) {tst_res (TINFO ,"Missing kernel %s" , kconfigs[i]); abort_test =1 ;continue ; } -if (results[i].match =='n' ) { +if (vars[i].choice =='n' ) {tst_res (TINFO ,"Kernel %s is not set" , kconfigs[i]); abort_test =1 ;continue ;@@ -263,21 +249,21 @@ void tst_kconfig_check(const char *const kconfigs[])const char *val =strchr (kconfigs[i],'=' );if (val) { -char match ='v' ; +char choice ='v' ; val++;if (!strcmp (val,"y" )) - match ='y' ; + choice ='y' ;if (!strcmp (val,"m" )) - match ='m' ; + choice ='m' ; -if (compare_res (&results[i], kconfigs[i], match, val)) +if (compare_res (&vars[i], kconfigs[i], choice, val)) abort_test =1 ; } -free (results[i].value); +free (vars[i].val); }
Quoted 6 lines
Quoted 3 lines
lib/tst_kconfig.c +0
-0if (abort_test)Signature · 1 line
2.26.2I suppose most of the problems here stem from the original code, but your patch may as well clear it up :-)
Actually the clear way how to fix this is in a separate patch so that logical changes are split into different patches.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hello,
Quoted 22 lines · Cyril Hrubis
Quoted 11 lines
Quoted 11 lines
lib/tst_kconfig.c +4
-4-static inline int match (struct match *match,const char *conf, -struct tst_kconfig_res *result,const char *line) +static inline int kconfig_parse_line (const char *line, +struct tst_kconfig_var *vars, +unsigned int vars_len) { -if (match->match) -return 0 ; +unsigned int i;Quoted 10 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 117
Quoted 5 lines
lib/tst_kconfig.c +4
-1-const char *cfg =strstr (line,"CONFIG_" ); +for (i =0 ; i < vars_len; i++) { +if (!strncmp (vars[i].id, line, vars[i].id_len)) { +const char *val = &line[vars[i].id_len]; +It is valid to have '
CONFIG_VAR= y'. We should probably tokenize the lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
Quoted 4 lines
I guess that it's techincally possible to have a whitespaces there, but will not happen unless you hand-edit the config file before compilation, which I doubt will ever happen.
It can also happen if someone has their own script to modify the config. At any rate, if you are confident that it will never happen then there should be no problem failing hard if it does.
Quoted 12 lines
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 125
Quoted 8 lines
lib/tst_kconfig.c +8
-0+switch (val[0 ]) { +case '=' : +break ; +case ' ' : +if (is_set (val,"is not set" )) { + vars[i].choice ='n' ; +return 1 ; + }Typically such lines begin with a comment '#' and I don't see where that is handled. Possibly this will only match non standard configs?
Quoted 5 lines
It does work actually, since we use
strstr()to get the "CONFIG_" prefix from each line of the configuration, but I guess this needs to be fixed anyways since we would detect "#CONFIG_FOO=y" as enabled config feature even if it's commented. Again this will not happen unless you hand-edit the file, but it's probably worth fixing in a follow up patch.
We don't actually use the result of strstr anymore?
Quoted 113 lines
Quoted 102 lines
Quoted 102 lines
lib/tst_kconfig.c +23
-63+return 1 ; +/* vars[i].id may be prefix to longer config var */ +default : +return 0 ; + } -if (!cfg) -return 0 ; +if (is_set (val,"=y" )) { + vars[i].choice ='y' ; +return 1 ; + } -if (strncmp (cfg, conf, match->len)) -return 0 ; +if (is_set (val,"=m" )) { + vars[i].choice ='m' ; +return 1 ; + } -const char *val = &cfg[match->len]; + vars[i].choice ='v' ; + vars[i].val =strndup (val+1 ,strlen (val)-2 ); -switch (cfg[match->len]) { -case '=' : -break ; -case ' ' : -if (is_set (val,"is not set" )) { - result->match ='n' ; - goto match; +return 1 ; } -/* fall through */ -default : -return 0 ; - } - -if (is_set (val,"=y" )) { - result->match ='y' ; - goto match; } -if (is_set (val,"=m" )) { - result->match ='m' ; - goto match; - } - - result->match ='v' ; - result->value =strndup (val+1 ,strlen (val)-2 ); - -match: - match->match =1 ; -return 1 ; +return 0 ; } -void tst_kconfig_read (const char *const *kconfigs, -struct tst_kconfig_res results[],size_t cnt) +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len) { -struct match matches[cnt]; -FILE *fp; -unsigned int i, j; -char buf[1024 ]; - -for (i =0 ; i < cnt; i++) { -const char *val =strchr (kconfigs[i],'=' ); - -if (strncmp ("CONFIG_" , kconfigs[i],7 )) -tst_brk (TBROK ,"Invalid config string '%s'" , kconfigs[i]); +char line[128 ]; +unsigned int vars_found =0 ; - matches[i].match =0 ; - matches[i].len =strlen (kconfigs[i]); - -if (val) { - matches[i].val = val +1 ; - matches[i].len -=strlen (val); - } - - results[i].match =0 ; - results[i].value =NULL ; - } - - fp =open_kconfig (); +FILE *fp =open_kconfig ();if (!fp)tst_brk (TBROK ,"Cannot parse kernel .config" ); -while (fgets (buf,sizeof (buf), fp)) { -for (i =0 ; i < cnt; i++) { -if (match (&matches[i], kconfigs[i], &results[i], buf)) { -for (j =0 ; j < cnt; j++) { -if (matches[j].match) -break ; - } +while (fgets (line,sizeof (line), fp)) { +char *cfg =strstr (line,"CONFIG_" );Quoted 10 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 165
Quoted 6 lines
lib/tst_kconfig.c +2
-4-if (j == cnt) - goto exit; - } - } +if (!cfg) +continue ;This filtering seems unecessary and maybe will hide some corner cases because it reduces kconfig_parses_line's exposure. Also practically every line has '
CONFIG_' in it.
Quoted 2 lines
Not really, there are empty lines and plenty of comments in the file generated by kernel infrastructure.
It seems about 80-90% of lines contain CONFIG_, however if you pass it to kconfig_parse_line then this makes more sense. Still I think with proper parsing this shouldn't be there.
Quoted 13 lines
Quoted 5 lines
Quoted 5 lines
lib/tst_kconfig.c +3
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++;Quoted 7 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 3 lines
lib/tst_kconfig.c +2
-0+if (vars_found == vars_len) + goto exit; }Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Quoted 3 lines
Well we do expect well formatted .config file from a start, if you hand edit it and put whitespaces into unexpected places more things may fail.
Kernel build system seems to have no problem with it. More generally though we should fail hard if there is something unexpected, not produce TCONF which people don't check.
Quoted 112 lines
Quoted 105 lines
Quoted 105 lines
exit:
lib/tst_kconfig.c +39
-18@@ -219,42 +184,63 @@ static size_t array_len(const char *const kconfigs[])return i; } -static int compare_res (struct tst_kconfig_res *res,const char *kconfig, -char match,const char *val) +static int compare_res (struct tst_kconfig_var *var,const char *kconfig, +char choice,const char *val) { -if (res->match != match) { -tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, res->match); +if (var->choice != choice) { +tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, var->choice);return 1 ; } -if (match !='v' ) +if (choice !='v' )return 0 ; -if (strcmp (res->value, val)) { -tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, res->value); +if (strcmp (var->val, val)) { +tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, var->val);return 1 ; }return 0 ; } +static inline unsigned int get_len (const char * kconfig) +{ +char *sep =index (kconfig,'=' ); + +if (!sep) +return strlen (kconfig); + +return sep - kconfig; +} +void tst_kconfig_check (const char *const kconfigs[]) { -size_t cnt =array_len (kconfigs); -struct tst_kconfig_res results[cnt]; +size_t vars_cnt =array_len (kconfigs); +struct tst_kconfig_var vars[vars_cnt];unsigned int i;int abort_test =0 ; -tst_kconfig_read (kconfigs, results, cnt); +memset (vars,0 ,sizeof (*vars) * vars_cnt); + +for (i =0 ; i < vars_cnt; i++) { + vars[i].id_len =get_len (kconfigs[i]); + +if (vars[i].id_len >=sizeof (vars[i].id)) +tst_brk (TBROK ,"kconfig var id too long!" ); + +strncpy (vars[i].id, kconfigs[i], vars[i].id_len); + } + +tst_kconfig_read (vars, vars_cnt); -for (i =0 ; i < cnt; i++) { -if (results[i].match ==0 ) { +for (i =0 ; i < vars_cnt; i++) { +if (vars[i].choice ==0 ) {tst_res (TINFO ,"Missing kernel %s" , kconfigs[i]); abort_test =1 ;continue ; } -if (results[i].match =='n' ) { +if (vars[i].choice =='n' ) {tst_res (TINFO ,"Kernel %s is not set" , kconfigs[i]); abort_test =1 ;continue ;@@ -263,21 +249,21 @@ void tst_kconfig_check(const char *const kconfigs[])const char *val =strchr (kconfigs[i],'=' );if (val) { -char match ='v' ; +char choice ='v' ; val++;if (!strcmp (val,"y" )) - match ='y' ; + choice ='y' ;if (!strcmp (val,"m" )) - match ='m' ; + choice ='m' ; -if (compare_res (&results[i], kconfigs[i], match, val)) +if (compare_res (&vars[i], kconfigs[i], choice, val)) abort_test =1 ; } -free (results[i].value); +free (vars[i].val); }Quoted 6 lines
Quoted 3 lines
lib/tst_kconfig.c +0
-0if (abort_test)Signature · 1 line
2.26.2I suppose most of the problems here stem from the original code, but your patch may as well clear it up :-)
Quoted 2 lines
Actually the clear way how to fix this is in a separate patch so that logical changes are split into different patches.
I suppose that elements of the boolean parser can be used to parse the kconfig and it can be combined (in a later patch). It's kind of unecessary to parse a config file into RPN, but will work perfectly well so we can share some code here.
Signature · 2 lines
Thank you, Richard.
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hi!
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
Quoted 8 lines
Quoted 4 lines
I guess that it's techincally possible to have a whitespaces there, but will not happen unless you hand-edit the config file before compilation, which I doubt will ever happen.
It can also happen if someone has their own script to modify the config. At any rate, if you are confident that it will never happen then there should be no problem failing hard if it does.
It would be probably easier to eat the whitespace around the = if present. But still I would ignore anything that isn't correct variable assignment, since such config would fail kernel compilation anyways.
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 125
Quoted 8 lines
lib/tst_kconfig.c +8
-0+switch (val[0 ]) { +case '=' : +break ; +case ' ' : +if (is_set (val,"is not set" )) { + vars[i].choice ='n' ; +return 1 ; + }Typically such lines begin with a comment '#' and I don't see where that is handled. Possibly this will only match non standard configs?
Quoted 7 lines
Quoted 5 lines
It does work actually, since we use
strstr()to get the "CONFIG_" prefix from each line of the configuration, but I guess this needs to be fixed anyways since we would detect "#CONFIG_FOO=y" as enabled config feature even if it's commented. Again this will not happen unless you hand-edit the file, but it's probably worth fixing in a follow up patch.We don't actually use the result of strstr anymore?
Ah right, that's a bug, the cfg should be passed to the kconfig_parse_line() instead, at least that's how the previous version worked in order to differentiate between unset and unknown variables.
Quoted 112 lines
Quoted 112 lines
Quoted 111 lines
Quoted 97 lines
lib/tst_kconfig.c +21
-62+return 1 ; +/* vars[i].id may be prefix to longer config var */ +default : +return 0 ; + } -if (!cfg) -return 0 ; +if (is_set (val,"=y" )) { + vars[i].choice ='y' ; +return 1 ; + } -if (strncmp (cfg, conf, match->len)) -return 0 ; +if (is_set (val,"=m" )) { + vars[i].choice ='m' ; +return 1 ; + } -const char *val = &cfg[match->len]; + vars[i].choice ='v' ; + vars[i].val =strndup (val+1 ,strlen (val)-2 ); -switch (cfg[match->len]) { -case '=' : -break ; -case ' ' : -if (is_set (val,"is not set" )) { - result->match ='n' ; - goto match; +return 1 ; } -/* fall through */ -default : -return 0 ; - } - -if (is_set (val,"=y" )) { - result->match ='y' ; - goto match; } -if (is_set (val,"=m" )) { - result->match ='m' ; - goto match; - } - - result->match ='v' ; - result->value =strndup (val+1 ,strlen (val)-2 ); - -match: - match->match =1 ; -return 1 ; +return 0 ; } -void tst_kconfig_read (const char *const *kconfigs, -struct tst_kconfig_res results[],size_t cnt) +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len) { -struct match matches[cnt]; -FILE *fp; -unsigned int i, j; -char buf[1024 ]; - -for (i =0 ; i < cnt; i++) { -const char *val =strchr (kconfigs[i],'=' ); - -if (strncmp ("CONFIG_" , kconfigs[i],7 )) -tst_brk (TBROK ,"Invalid config string '%s'" , kconfigs[i]); +char line[128 ]; +unsigned int vars_found =0 ; - matches[i].match =0 ; - matches[i].len =strlen (kconfigs[i]); - -if (val) { - matches[i].val = val +1 ; - matches[i].len -=strlen (val); - } - - results[i].match =0 ; - results[i].value =NULL ; - } - - fp =open_kconfig (); +FILE *fp =open_kconfig ();if (!fp)tst_brk (TBROK ,"Cannot parse kernel .config" ); -while (fgets (buf,sizeof (buf), fp)) { -for (i =0 ; i < cnt; i++) { -if (match (&matches[i], kconfigs[i], &results[i], buf)) { -for (j =0 ; j < cnt; j++) { -if (matches[j].match) -break ;lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 165
Quoted 10 lines
lib/tst_kconfig.c +4
-5- } +while (fgets (line,sizeof (line), fp)) { +char *cfg =strstr (line,"CONFIG_" ); -if (j == cnt) - goto exit; - } - } +if (!cfg) +continue ;This filtering seems unecessary and maybe will hide some corner cases because it reduces kconfig_parses_line's exposure. Also practically every line has '
CONFIG_' in it.
Quoted 6 lines
Quoted 2 lines
Not really, there are empty lines and plenty of comments in the file generated by kernel infrastructure.
It seems about 80-90% of lines contain
CONFIG_, however if you pass it tokconfig_parse_linethen this makes more sense. Still I think with proper parsing this shouldn't be there.
What exactly do you mean by a proper parsing?
The file is format is very simple each line starts either with # which is a comment or consists of 'key=val' pair and the key is by definition prefixed with CONFIG_.
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 7 lines
lib/tst_kconfig.c +5
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++; +if (vars_found == vars_len) + goto exit; }Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Quoted 7 lines
Quoted 3 lines
Well we do expect well formatted .config file from a start, if you hand edit it and put whitespaces into unexpected places more things may fail.
Kernel build system seems to have no problem with it. More generally though we should fail hard if there is something unexpected, not produce TCONF which people don't check.
Even if we do I do not think that we should care about anything but syntactically correct input, since if you modify the file after kernel compilation you have lost anyways.
Quoted 10 lines
Quoted 5 lines
Quoted 2 lines
I suppose most of the problems here stem from the original code, but your patch may as well clear it up :-)
Actually the clear way how to fix this is in a separate patch so that logical changes are split into different patches.
I suppose that elements of the boolean parser can be used to parse the kconfig and it can be combined (in a later patch). It's kind of unecessary to parse a config file into RPN, but will work perfectly well so we can share some code here.
I do not get what you are trying to say. Are you saying that we should tokenize the input? I do not think that this is necessary since the file format is pretty simple.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hi,
Quoted 9 lines
Quoted 7 lines
Quoted 7 lines
Quoted 3 lines
lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
I guess that it's techincally possible to have a whitespaces there, but will not happen unless you hand-edit the config file before compilation, which I doubt will ever happen.
Quoted 7 lines
Quoted 3 lines
It can also happen if someone has their own script to modify the config. At any rate, if you are confident that it will never happen then there should be no problem failing hard if it does.
It would be probably easier to eat the whitespace around the = if present. But still I would ignore anything that isn't correct variable assignment, since such config would fail kernel compilation anyways.
+1
+ I use ./scripts/config --enable | --disable ... to avoid problems with incorrect config.
Quoted 16 lines
Quoted 15 lines
Quoted 15 lines
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 7 lines
lib/tst_kconfig.c +5
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++; +if (vars_found == vars_len) + goto exit; }Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Well we do expect well formatted .config file from a start, if you hand edit it and put whitespaces into unexpected places more things may fail.
Quoted 7 lines
Quoted 3 lines
Kernel build system seems to have no problem with it. More generally though we should fail hard if there is something unexpected, not produce TCONF which people don't check.
Even if we do I do not think that we should care about anything but syntactically correct input, since if you modify the file after kernel compilation you have lost anyways.
+1
Kind regards,
Petr
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
In reply to Cyril HrubisHello,
Quoted 10 lines · Cyril Hrubis
Hi!
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
lines first to remove whitespace issues and expose the parser to all possible variable name symbols and values instead of just the ones which appear in our current tests.
I guess that it's techincally possible to have a whitespaces there, but will not happen unless you hand-edit the config file before compilation, which I doubt will ever happen.
Quoted 7 lines
Quoted 3 lines
It can also happen if someone has their own script to modify the config. At any rate, if you are confident that it will never happen then there should be no problem failing hard if it does.
It would be probably easier to eat the whitespace around the = if present. But still I would ignore anything that isn't correct variable assignment, since such config would fail kernel compilation anyways.
Works for me :-)
Quoted 137 lines
Quoted 13 lines
Quoted 13 lines
Quoted 12 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 125
Quoted 9 lines
lib/tst_kconfig.c +8
-0+switch (val[0 ]) { +case '=' : +break ; +case ' ' : +if (is_set (val,"is not set" )) { + vars[i].choice ='n' ; +return 1 ; + }Typically such lines begin with a comment '#' and I don't see where that is handled. Possibly this will only match non standard configs?
Quoted 7 lines
Quoted 5 lines
It does work actually, since we use
strstr()to get the "CONFIG_" prefix from each line of the configuration, but I guess this needs to be fixed anyways since we would detect "#CONFIG_FOO=y" as enabled config feature even if it's commented. Again this will not happen unless you hand-edit the file, but it's probably worth fixing in a follow up patch.We don't actually use the result of strstr anymore?
Ah right, that's a bug, the cfg should be passed to the
kconfig_parse_line()instead, at least that's how the previous version worked in order to differentiate between unset and unknown variables.Quoted 112 lines
Quoted 112 lines
Quoted 111 lines
Quoted 97 lines
lib/tst_kconfig.c +21
-62+return 1 ; +/* vars[i].id may be prefix to longer config var */ +default : +return 0 ; + } -if (!cfg) -return 0 ; +if (is_set (val,"=y" )) { + vars[i].choice ='y' ; +return 1 ; + } -if (strncmp (cfg, conf, match->len)) -return 0 ; +if (is_set (val,"=m" )) { + vars[i].choice ='m' ; +return 1 ; + } -const char *val = &cfg[match->len]; + vars[i].choice ='v' ; + vars[i].val =strndup (val+1 ,strlen (val)-2 ); -switch (cfg[match->len]) { -case '=' : -break ; -case ' ' : -if (is_set (val,"is not set" )) { - result->match ='n' ; - goto match; +return 1 ; } -/* fall through */ -default : -return 0 ; - } - -if (is_set (val,"=y" )) { - result->match ='y' ; - goto match; } -if (is_set (val,"=m" )) { - result->match ='m' ; - goto match; - } - - result->match ='v' ; - result->value =strndup (val+1 ,strlen (val)-2 ); - -match: - match->match =1 ; -return 1 ; +return 0 ; } -void tst_kconfig_read (const char *const *kconfigs, -struct tst_kconfig_res results[],size_t cnt) +void tst_kconfig_read (struct tst_kconfig_var vars[],size_t vars_len) { -struct match matches[cnt]; -FILE *fp; -unsigned int i, j; -char buf[1024 ]; - -for (i =0 ; i < cnt; i++) { -const char *val =strchr (kconfigs[i],'=' ); - -if (strncmp ("CONFIG_" , kconfigs[i],7 )) -tst_brk (TBROK ,"Invalid config string '%s'" , kconfigs[i]); +char line[128 ]; +unsigned int vars_found =0 ; - matches[i].match =0 ; - matches[i].len =strlen (kconfigs[i]); - -if (val) { - matches[i].val = val +1 ; - matches[i].len -=strlen (val); - } - - results[i].match =0 ; - results[i].value =NULL ; - } - - fp =open_kconfig (); +FILE *fp =open_kconfig ();if (!fp)tst_brk (TBROK ,"Cannot parse kernel .config" ); -while (fgets (buf,sizeof (buf), fp)) { -for (i =0 ; i < cnt; i++) { -if (match (&matches[i], kconfigs[i], &results[i], buf)) { -for (j =0 ; j < cnt; j++) { -if (matches[j].match) -break ;lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 165
Quoted 10 lines
lib/tst_kconfig.c +4
-5- } +while (fgets (line,sizeof (line), fp)) { +char *cfg =strstr (line,"CONFIG_" ); -if (j == cnt) - goto exit; - } - } +if (!cfg) +continue ;This filtering seems unecessary and maybe will hide some corner cases because it reduces kconfig_parses_line's exposure. Also practically every line has '
CONFIG_' in it.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
Not really, there are empty lines and plenty of comments in the file generated by kernel infrastructure.
It seems about 80-90% of lines contain
CONFIG_, however if you pass it tokconfig_parse_linethen this makes more sense. Still I think with proper parsing this shouldn't be there.What exactly do you mean by a proper parsing?
Tokenize it and remove whitespace.
Quoted 35 lines
The file is format is very simple each line starts either with # which is a comment or consists of 'key=val' pair and the key is by definition prefixed with
CONFIG_.Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
lib/tst_kconfig.c static int is_set(const char *str, const char *val) · line 172
Quoted 7 lines
lib/tst_kconfig.c +5
-0+ +if (kconfig_parse_line (line, vars, vars_len)) + vars_found++; +if (vars_found == vars_len) + goto exit; }Generally, this approach seems like to result in spurious TCONFs. We need to properly parse the file and fail if some line can't be interpreted.
Quoted 7 lines
Quoted 3 lines
Well we do expect well formatted .config file from a start, if you hand edit it and put whitespaces into unexpected places more things may fail.
Kernel build system seems to have no problem with it. More generally though we should fail hard if there is something unexpected, not produce TCONF which people don't check.
Even if we do I do not think that we should care about anything but syntactically correct input, since if you modify the file after kernel compilation you have lost anyways.
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines
I suppose most of the problems here stem from the original code, but your patch may as well clear it up :-)
Actually the clear way how to fix this is in a separate patch so that logical changes are split into different patches.
Quoted 8 lines
Quoted 4 lines
I suppose that elements of the boolean parser can be used to parse the kconfig and it can be combined (in a later patch). It's kind of unecessary to parse a config file into RPN, but will work perfectly well so we can share some code here.
I do not get what you are trying to say. Are you saying that we should tokenize the input? I do not think that this is necessary since the file format is pretty simple.
Yes or atleast test the assumption you won't find configs with spaces or other wierd stuff in by throwing an error if we find something unexpected. If someone has a broken config we can tell them that.
Signature · 2 lines
Thank you, Richard.
PATCH 1/3 lib/tst_kconfig: Rewrite the parser internals
Hi!
Quoted 7 lines
Quoted 3 lines
I do not get what you are trying to say. Are you saying that we should tokenize the input? I do not think that this is necessary since the file format is pretty simple.
Yes or atleast test the assumption you won't find configs with spaces or other wierd stuff in by throwing an error if we find something unexpected. If someone has a broken config we can tell them that.
I guess I can make it a bit more robust in a follow up patch.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH 2/3 lib: Add generic boolean expression parser and eval
In reply to Cyril HrubisAdd a simple and generic boolean expression parser and evaluator. This is a second step in order to implement more complex kconfig expressions, but since we are likely to reuse the parser for other purposes in the future it's implemented as a generic boolean parser.
--- include/tst_bool_expr.h | 80 +++++ lib/newlib_tests/.gitignore | 1 + lib/newlib_tests/tst_bool_expr.c | 127 ++++++++ lib/tst_bool_expr.c | 504 +++++++++++++++++++++++++++++++ 4 files changed, 712 insertions(+) create mode 100644 include/tst_bool_expr.h create mode 100644 lib/newlib_tests/tst_bool_expr.c create mode 100644 lib/tst_bool_expr.c
include/tst_bool_expr.h new file +80 -0
@@ -0,0 +1,80 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* +* Copyright (c) 2020 Cyril Hrubis <[email protected]> +*/ + +#ifndef TST_BOOL_EXPR_H__ +#define TST_BOOL_EXPR_H__ + +enum tst_op { +TST_OP_NOT , +TST_OP_AND , +TST_OP_OR , +TST_OP_VAR , +/* Used only internally */ +TST_OP_LPAR , +TST_OP_RPAR , +}; + +struct tst_expr { +enum tst_op op; +struct tst_expr *next; +char *err; +void *priv; +char val[]; +}; + +/* +* Parses an boolean expression and returns a simplified RPN version. +* +* If expression is not valid the call prints error into stderr and returns +* NULL. On success pointer to an expression is returned which can be evaluated +* by the tst_bool_expr_eval() function and has to be later freed by the +* caller. +* +* The boolean expression can consists of: +* +* - unary negation opeartion ! +* - two binary operations & and | +* - correct sequence of parentheses () +* - strings that are treated as boolean variables +* +* e.g. '(A | B) & C' or 'Variable_1 & Variable_2' are both a valid boolean +* expressions. +* +* @expr String containing a boolean expression to be parsed. +* @return Pointer to an RPN expression. +*/ +struct tst_expr *tst_bool_expr_parse (const char *expr); + +/* +* Prints an string representation of the expression into a FILE. +* +* @param A FILE to print to. +* @expr An expression to print. +*/ +void tst_bool_expr_print (FILE *f,struct tst_expr *expr); + +/* +* Evaluates an expression given a map for variables. +* +* The call will fail if: +* - map function returns -1 which indicates undefined variable +* - the eval function runs out of stack +* +* @param expr Boolean expression in RPN. +* @param map Mapping function for boolean variables. +* +* @return Returns 0 or 1 if expression was evaluated correctly and -1 on error. +*/ +int tst_bool_expr_eval (struct tst_expr *expr, +int (*map)(struct tst_expr *var)); + +/* +* Frees the memory allocated by the tst_bool_expr_parse(). +* +* @param Boolean expression. +*/ +void tst_bool_expr_free (struct tst_expr *expr); + +#endif /* TST_BOOL_EXPR_H__ */
lib/newlib_tests/.gitignore +1 -0
@@ -33,3 +33,4 @@ test_exec_child test_kconfig variant test_guarded_buf +tst_bool_expr
lib/newlib_tests/tst_bool_expr.c new file +127 -0
127 lines not on this page · raw message
lib/tst_bool_expr.c new file +504 -0
504 lines not on this page · raw message
Signature · 1 line
2.26.2
PATCH 2/3 lib: Add generic boolean expression parser and eval
Hello,
Quoted 4 lines · Cyril Hrubis
Add a simple and generic boolean expression parser and evaluator. This is a second step in order to implement more complex kconfig expressions, but since we are likely to reuse the parser for other purposes in the future it's implemented as a generic boolean parser.
This looks really excellent in general!
Quoted 31 lines
Signed-off-by Cyril Hrubis <[email protected]>--- include/tst_bool_expr.h | 80 +++++ lib/newlib_tests/.gitignore | 1 + lib/newlib_tests/tst_bool_expr.c | 127 ++++++++ lib/tst_bool_expr.c | 504 +++++++++++++++++++++++++++++++ 4 files changed, 712 insertions(+) create mode 100644 include/tst_bool_expr.h create mode 100644 lib/newlib_tests/tst_bool_expr.c create mode 100644 lib/tst_bool_expr.cinclude/tst_bool_expr.h new file +13
-0@@ -0,0 +1,80 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* +* Copyright (c) 2020 Cyril Hrubis <[email protected]> +*/ + +#ifndef TST_BOOL_EXPR_H__ +#define TST_BOOL_EXPR_H__ + +enum tst_op { +TST_OP_NOT , +TST_OP_AND , +TST_OP_OR , + TST_OP_VAR,
include/tst_bool_expr.h line 23
Quoted 10 lines
include/tst_bool_expr.h new file +10
-0+/* Used only internally */ +TST_OP_LPAR , + TST_OP_RPAR, +}; + +struct tst_expr { +enum tst_op op; +struct tst_expr *next; +char *err; +void *priv;
I'm not sure if this is used?
include/tst_bool_expr.h line 24
Quoted 1 line
include/tst_bool_expr.h new file +1
-0+char val[];
This could be replaced by 'struct tok', see below.
Quoted 163 lines
include/tst_bool_expr.h new file +56
-0+}; + +/* +* Parses an boolean expression and returns a simplified RPN version. +* +* If expression is not valid the call prints error into stderr and returns +* NULL. On success pointer to an expression is returned which can be evaluated +* by the tst_bool_expr_eval() function and has to be later freed by the +* caller. +* +* The boolean expression can consists of: +* +* - unary negation opeartion ! +* - two binary operations & and | +* - correct sequence of parentheses () +* - strings that are treated as boolean variables +* +* e.g. '(A | B) & C' or 'Variable_1 & Variable_2' are both a valid boolean +* expressions. +* +* @expr String containing a boolean expression to be parsed. +* @return Pointer to an RPN expression. +*/ +struct tst_expr *tst_bool_expr_parse (const char *expr); + +/* +* Prints an string representation of the expression into a FILE. +* +* @param A FILE to print to. +* @expr An expression to print. +*/ +void tst_bool_expr_print (FILE *f,struct tst_expr *expr); + +/* +* Evaluates an expression given a map for variables. +* +* The call will fail if: +* - map function returns -1 which indicates undefined variable +* - the eval function runs out of stack +* +* @param expr Boolean expression in RPN. +* @param map Mapping function for boolean variables. +* +* @return Returns 0 or 1 if expression was evaluated correctly and -1 on error. +*/ +int tst_bool_expr_eval (struct tst_expr *expr, +int (*map)(struct tst_expr *var)); + +/* +* Frees the memory allocated by the tst_bool_expr_parse(). +* +* @param Boolean expression. +*/ +void tst_bool_expr_free (struct tst_expr *expr); + +#endif /* TST_BOOL_EXPR_H__ */ lib/newlib_tests/.gitignore +1
-0@@ -33,3 +33,4 @@ test_exec_child test_kconfig variant test_guarded_buf +tst_bool_exprlib/newlib_tests/tst_bool_expr.c new file +92
-0@@ -0,0 +1,127 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* +* Copyright (c) 2017 Cyril Hrubis <[email protected]> +*/ + +/* +* Basic unit test for the tst_strstatus() function. +*/ + +#include <string.h> +#include <stdio.h> +#include "tst_test.h" +#include "tst_bool_expr.h" + +static int a, b, c; + +static int map (struct tst_expr *var) +{ +if (!strcmp (var->val,"A" )) +return a; + +if (!strcmp (var->val,"B" )) +return b; + +if (!strcmp (var->val,"C" )) +return c; + +if (!strcmp (var->val,"True" )) +return 1 ; + +if (!strcmp (var->val,"False" )) +return 0 ; + +return -1 ; +} + +static void parse_fail (const char *expr) +{ +struct tst_expr *res; + +tst_res (TINFO ,"Parsing '%s'" , expr); + + res =tst_bool_expr_parse (expr); + +if (res) { +printf ("In RPN: " ); +tst_bool_expr_print (stdout, res); +printf ("\n" ); +tst_bool_expr_free (res); +tst_res (TFAIL ,"Expression was parsed" ); + }else { +tst_res (TPASS ,"Parser returned an error" ); + } +} + +static void do_eval_test (const char *expr_str,int set_a,int set_b,int set_c,int exp_res) +{ +struct tst_expr *expr; +int res; + + a = set_a; + b = set_b; + c = set_c; + +tst_res (TINFO ,"'%s' A=%i B=%i C=%i == %i" , expr_str, a, b, c, exp_res); + + expr =tst_bool_expr_parse (expr_str); + +if (!expr) { +tst_res (TFAIL ,"Parser returned error" ); +return ; + } + +printf ("In RPN: " ); +tst_bool_expr_print (stdout, expr); +printf ("\n" ); + + res =tst_bool_expr_eval (expr, map); + +if (res == exp_res) +tst_res (TPASS ,"Got %i" , res); +else +tst_res (TFAIL ,"Got %i" , res); + +tst_bool_expr_free (expr); +} + +static void do_test (void ) +{ +do_eval_test ("(A | B) & !!C" ,0 ,0 ,0 ,0 ); +do_eval_test ("(A | B) & !!C" ,1 ,0 ,1 ,1 ); +do_eval_test ("!A & B" ,1 ,0 ,0 ,0 );
lib/newlib_tests/tst_bool_expr.c line 102
Quoted 10 lines
lib/newlib_tests/tst_bool_expr.c new file +10
-0+do_eval_test ("!A & B" ,0 ,1 ,0 ,1 ); +do_eval_test ("A & !B" ,1 ,0 ,0 ,1 ); +do_eval_test ("!!A & !!B" ,0 ,1 ,0 ,0 ); +do_eval_test ("!!A & !!B" ,1 ,1 ,0 ,1 ); +do_eval_test ("!(A & B) & C" ,1 ,1 ,0 ,0 ); +do_eval_test ("A & (B | C)" ,1 ,1 ,0 ,1 ); +do_eval_test ("((((A)))&(B))" ,1 ,1 ,0 ,1 ); +do_eval_test ("True | A" ,0 ,0 ,0 ,1 ); +do_eval_test ("False & A" ,1 ,0 ,0 ,0 ); +do_eval_test ("! Undefined" ,0 ,0 ,0 ,-1 );
Can we also test "A & B | C" without brackets?
Quoted 52 lines
lib/newlib_tests/tst_bool_expr.c new file +25
-0+ +parse_fail ("A!" ); +parse_fail ("A &" ); +parse_fail ("A B" ); +parse_fail ("A ) B" ); +parse_fail ("A ( B" ); +parse_fail ("A ( B )" ); +parse_fail ("A |" ); +parse_fail ("A ! B" ); +parse_fail ("A! & B" ); +parse_fail ("A & | B" ); +parse_fail ("A & (B |)" ); +parse_fail ("A & ( | B)" ); +parse_fail ("A & B &" ); +parse_fail ("((A )" ); +parse_fail ("& A" ); +parse_fail ("! &" ); +parse_fail (")" ); +parse_fail ("| A" ); +parse_fail ("" ); +} + +static struct tst_test test = { + .test_all = do_test, +};lib/tst_bool_expr.c new file +21
-0@@ -0,0 +1,504 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* +* Copyright (c) 2020 Cyril Hrubis <[email protected]> +*/ +/* +* Boolean expression is evaluated in three steps. +* +* First of all the string containing the expression is tokenized. +* +* Secondly the the expression is transformed to a postfix (RPN) notation by +* the shunting yard algorithm and the correctness of the expression is checked +* during the transformation as well. The fact that parenthesis are matched is +* asserted by the shunting yard algorithm itself while the rest is checked +* simply by checking if the preceding token is in a set of allowed tokens. +* This could be thought of as a simple open-coded state machine. +* +* An expression in the RPN form can be evaluated given a variable mapping +* function. The evaluation ignores most of errors because invalid expression +* will be rejected in the second step. +*/ +
lib/tst_bool_expr.c line 31
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include "tst_bool_expr.h" + +#define MAX_TOK 1024 + +struct tok { +unsigned int pos; +char buf[MAX_TOK ];
Instead we could save an index into the input string here and record the length. Then there is no need to copy the string or guess a suitable buffer length and we record the original token location for error reporting (although it seems you reconstruct the expression so it's not so useful).
Ofcourse that assumes the original string will remain in memory, but usually it will be a static string in tst_test. If we use the same parser for .config, then it still could just be mmapped in until we have finished with it.
I guess if we used the same tokenizer for the concurrent executor then the original string may not exist, but that can be dealt with later.
Quoted 15 lines
lib/tst_bool_expr.c new file +15
-0+}; + +static inline void tok_append (struct tok *tok,char c) +{ +if (tok->pos +2 >=MAX_TOK ) { + tok->buf[tok->pos+1 ] =0 ; +fprintf (stderr,"Truncating token '%s'!" , tok->buf); + } + + tok->buf[tok->pos++] = c; +} + +static inline char *tok_get (struct tok *tok) +{ +if (!tok->pos)
lib/tst_bool_expr.c line 56
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+return NULL ; + + tok->buf[tok->pos] ='\0' ; + + tok->pos =0 ; + +return tok->buf; +} + +static struct tst_expr *new_var (const char *val)
This could be modifed to accept 'struct tok' instead of a null terminated string. In any case it shouldn't the arg be const?
Quoted 4 lines
lib/tst_bool_expr.c new file +4
-0+{ +struct tst_expr *ret; + +if (!val)
lib/tst_bool_expr.c line 70
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+return NULL ; + + ret =malloc (sizeof (struct tst_expr ) +strlen (val) +1 ); +if (!ret) +return NULL ; + + ret->op =TST_OP_VAR ; + ret->next =NULL ; + ret->err =NULL ; +strcpy (ret->val, val);
and another string copy can be removed.
Quoted 9 lines
lib/tst_bool_expr.c new file +9
-0+ +return ret; +} + +enum tst_op char_to_op (char c) +{ +switch (c) { +case '(' : +return TST_OP_LPAR ;
lib/tst_bool_expr.c line 89
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case ')' : +return TST_OP_RPAR ; +case '&' : +return TST_OP_AND ; +case '|' : +return TST_OP_OR ; +case '!' : +return TST_OP_NOT ; +default : +return -1 ;
This should probably be an enum value like TST_OP_INVAL (still may be -1), otherwise it is likely to confuse static anlyses tools.
Quoted 153 lines
lib/tst_bool_expr.c new file +153
-0+ } +} + +static struct tst_expr *new_op (char c) +{ +struct tst_expr *ret; + + ret =malloc (sizeof (struct tst_expr )); +if (!ret) +return NULL ; + + ret->op =char_to_op (c); + ret->next =NULL ; + ret->err =NULL ; + +return ret; +} + +struct op_list { +struct tst_expr *first; +struct tst_expr *last; +unsigned int cnt; +}; + +static void op_list_append (struct op_list *list,struct tst_expr *val) +{ +if (!val) +return ; + +if (!list->first) + list->first = val; + +if (list->last) + list->last->next = val; + + list->last = val; + + list->cnt++; +} + +static void tokenize (const char *expr,struct op_list *ret) +{ +struct tok buf = {}; +size_t i; + +for (i =0 ; expr[i]; i++) { +switch (expr[i]) { +case '(' : +case ')' : +case '!' : +case '&' : +case '|' : +op_list_append (ret,new_var (tok_get (&buf))); +op_list_append (ret,new_op (expr[i])); +break ; +case '\t' : +case ' ' : +op_list_append (ret,new_var (tok_get (&buf))); +break ; +default : +tok_append (&buf, expr[i]); +break ; + } + } + +op_list_append (ret,new_var (tok_get (&buf))); +} + +void tst_bool_expr_print (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; + +for (i = expr; i; i = i->next) { +if (i->op !=TST_OP_VAR && prev_op) +fprintf (f," " ); + +switch (i->op) { +case TST_OP_AND : +fprintf (f,"&" ); +break ; +case TST_OP_OR : +fprintf (f,"|" ); +break ; +case TST_OP_NOT : +fprintf (f,"!" ); +break ; +case TST_OP_LPAR : +fprintf (f,"(" ); +break ; +case TST_OP_RPAR : +fprintf (f,")" ); +break ; +case TST_OP_VAR : +fprintf (f," %s " , i->val); +break ; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } +} + +static void tst_bool_expr_err (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; +unsigned int spaces =0 ; + +fprintf (f,"\n" ); + +for (i = expr; i; i = i->next) { +if (i->err) +break ; + +if (i->op !=TST_OP_VAR && prev_op) + spaces++; + +switch (i->op) { +case TST_OP_VAR : + spaces +=2 +strlen (i->val); +break ; +default : + spaces++; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } + +while (spaces--) +putc (' ' , f); + +fprintf (f,"^\n" ); +fprintf (f,"%s\n" , i->err); +} + +static inline void stack_push (struct tst_expr *stack[],unsigned int *stack_pos, +struct tst_expr *op) +{ + stack[(*stack_pos)++] = op; +} + +static inline int stack_empty (unsigned int stack_pos) +{ +return stack_pos ==0 ; +} + +static inline struct tst_expr *stack_pop(struct tst_expr *stack[],
lib/tst_bool_expr.c line 252
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+ unsigned int *stack_pos) +{ +if (stack_empty (*stack_pos)) +return NULL ; + +return stack[--(*stack_pos)]; +} + +static inline enum tst_op stack_top_op (struct tst_expr *stack[], +unsigned int stack_pos)
Just a nit, but usually this is called peek, right?
As we are peeking at the top/next entry without removing it.
lib/tst_bool_expr.c line 258
Quoted 6 lines
lib/tst_bool_expr.c new file +6
-0+{ +if (stack_empty (stack_pos)) +return -1 ; + +return stack[stack_pos -1 ]->op; +}
Perhaps we should copy & paste the dynamic preallocated vector we created for gfxprim? We are doing a bunch of mallocs and reinventing linked lists and stacks, which can all be represented by the vector IIRC.
lib/tst_bool_expr.c line 266
Quoted 8 lines
lib/tst_bool_expr.c new file +8
-0+ +/* +* This is a complete list of which tokens can happen before any of: +* - variable +* - left parentesis +* - negation +* +* The -1 represents start of the expression.
Then it should have an entry in the enum.
lib/tst_bool_expr.c line 268
Quoted 2 lines
lib/tst_bool_expr.c new file +2
-0+*/ +static inline int check_one (int op)
I guess there is no good name for this xD
Quoted 24 lines
lib/tst_bool_expr.c new file +24
-0+{ +switch (op) { +case TST_OP_AND : +case TST_OP_OR : +case TST_OP_NOT : +case -1 : +case TST_OP_LPAR : +return 0 ; +default : +return 1 ; + } +} + +/* +* And this checks for tokens that can happen before any of: +* - right parentesis +* - and +* - or +* +* This is also used to check that the last token in expression is correct one. +*/ +static inline int check_two (int op) +{ +switch (op) {
lib/tst_bool_expr.c line 302
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case TST_OP_VAR : +case TST_OP_RPAR : +return 1 ; +default : +return 0 ; + } +} + +static struct tst_expr *shunting_yard (struct op_list *list) +{
/* Translator stack */
lib/tst_bool_expr.c line 308
Quoted 6 lines
lib/tst_bool_expr.c new file +6
-0+struct tst_expr *stack[list->cnt]; +unsigned int stack_pos =0 ; +struct tst_expr *out[list->cnt +1 ]; +unsigned int out_pos =0 ; +struct tst_expr *pars[list->cnt]; +unsigned int pars_pos =0 ;
It seems we just push stuff to this stack then free everything at the end?
lib/tst_bool_expr.c line 311
Quoted 3 lines
lib/tst_bool_expr.c new file +3
-0+struct tst_expr *i; +unsigned int j; +int prev_op =-1 ;
enum tst_op prev_op = TST_OP_START;
lib/tst_bool_expr.c line 323
Quoted 12 lines
lib/tst_bool_expr.c new file +12
-0+ +for (i = list->first; i; i = i->next) { +switch (i->op) { +case TST_OP_VAR : +if (check_one (prev_op) && prev_op !=TST_OP_LPAR ) { + i->err ="Expected operation" ; + goto err; + } + +stack_push (out, &out_pos, i); + +/* pop all negations */
Clearly :-)
This is not the hardest thing to understand here!
Quoted 46 lines
lib/tst_bool_expr.c new file +46
-0+while (stack_top_op (stack, stack_pos) ==TST_OP_NOT ) +stack_push (out, &out_pos,stack_pop (stack, &stack_pos)); +break ; +case TST_OP_LPAR : +if (check_one (prev_op)) { + i->err ="Expected operation" ; + goto err; + } + +stack_push (stack, &stack_pos, i); +break ; +case TST_OP_RPAR : +if (!check_two (prev_op)) { + i->err ="Expected variable or )" ; + goto err; + } + +stack_push (pars, &pars_pos, i); + +/* pop everything till ( */ +for (;;) { +struct tst_expr *op =stack_pop (stack, &stack_pos); + +if (!op) { + i->err ="Missing (" ; + goto err; + } + +if (op->op ==TST_OP_LPAR ) { +stack_push (pars, &pars_pos, op); +break ; + } + +stack_push (out, &out_pos, op); + } + +/* pop all negations */ +while (stack_top_op (stack, stack_pos) ==TST_OP_NOT ) +stack_push (out, &out_pos,stack_pop (stack, &stack_pos)); +break ; +case TST_OP_NOT : +if (check_one (prev_op)) { + i->err ="Expected operation" ; + goto err; + } +stack_push (stack, &stack_pos, i);
lib/tst_bool_expr.c line 379
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+break ; +case TST_OP_AND : +case TST_OP_OR : +if (!check_two (prev_op)) { + i->err ="Expected variable or (" ; + goto err; + } + +/* pop all binary ops */ +for (;;) {
It seems that we can only have at most one previous binary op (i.e. '&' or '|') on the stack before '(' or NULL. Any additional ops after '(' or NULL are removed.
So the loop can be limited to two iterations and we can assert it never reaches a third.
lib/tst_bool_expr.c line 389
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+enum tst_op top_op; + +if (stack_empty (stack_pos)) +break ; + + top_op =stack_top_op (stack, stack_pos); + +if (top_op ==TST_OP_LPAR || + top_op ==TST_OP_NOT ) +break ;
'!'s are removed directly after a variable is seen or a '(' is removed. So it should be an error to find one on the stack at this point.
Quoted 117 lines
lib/tst_bool_expr.c new file +115
-0+ +stack_push (out, &out_pos,stack_pop (stack, &stack_pos)); + } +stack_push (stack, &stack_pos, i); +break ; + } + + prev_op = i->op; + } + +if (!check_two (list->last->op)) { + list->last->err ="Unfinished expression" ; + goto err; + } + +/* pop remaining operations */ +while ((i =stack_pop (stack, &stack_pos))) { +if (i->op ==TST_OP_LPAR ) { + i->err ="Missing )" ; + goto err; + } + +stack_push (out, &out_pos, i); + } + +/* free parentesis */ +for (j =0 ; j < pars_pos; j++) +free (pars[j]); + +/* reconstruct the list */ + out[out_pos] =NULL ; + +for (j =0 ; j < out_pos; j++) + out[j]->next = out[j +1 ]; + +return out[0 ]; +err: +return NULL ; +} + +struct tst_expr *tst_bool_expr_parse (const char *expr) +{ +struct op_list list = {}; +struct tst_expr *ret; + +tokenize (expr, &list); + +if (!list.first) +return NULL ; + + ret =shunting_yard (&list); + +if (!ret) { +tst_bool_expr_print (stderr, list.first); +tst_bool_expr_err (stderr, list.first); +tst_bool_expr_free (list.first); +return NULL ; + } + +return ret; +} + +#define MAX_STACK 16 + +int tst_bool_expr_eval (struct tst_expr *expr, +int (*map)(struct tst_expr *var)) +{ +struct tst_expr *i; +int stack[MAX_STACK ]; +int pos =-1 ; + +for (i = expr; i; i = i->next) { +switch (i->op) { +case TST_OP_NOT : + stack[pos] = !stack[pos]; +break ; +case TST_OP_OR : + stack[pos-1 ] = stack[pos] || stack[pos-1 ]; + pos--; +break ; +case TST_OP_AND : + stack[pos-1 ] = stack[pos] && stack[pos-1 ]; + pos--; +break ; +case TST_OP_VAR : +if (pos +1 >=MAX_STACK ) { +fprintf (stderr,"Eval out of stack!\n" ); +return -1 ; + } + + stack[++pos] =map (i); + +/* map reported undefined variable -> abort */ +if (stack[pos] ==-1 ) +return -1 ; +break ; +/* does not happen */ +default : +break ; + } + } + +return stack[0 ]; +} + +void tst_bool_expr_free (struct tst_expr *expr) +{ +struct tst_expr *i = expr, *tmp; + +while (i) { + tmp = i; + i = i->next; +free (tmp); + } +}Signature · 1 line
2.26.2
Again, looks really nice!
Signature · 2 lines
Thank you, Richard.
PATCH 2/3 lib: Add generic boolean expression parser and eval
Hello,
Quoted 11 lines
Quoted 10 lines · Cyril Hrubis
include/tst_bool_expr.h new file +10
-0+ +enum tst_op { +TST_OP_NOT , +TST_OP_AND , +TST_OP_OR , +TST_OP_VAR , +/* Used only internally */ +TST_OP_LPAR , +TST_OP_RPAR , +};
Quoted 8 lines
include/tst_bool_expr.h line 23
Quoted 6 lines
include/tst_bool_expr.h new file +6
-0+ +struct tst_expr { +enum tst_op op; +struct tst_expr *next; +char *err; +void *priv;I'm not sure if this is used?
I see it, ignore this.
Signature · 2 lines
Thank you, Richard.
PATCH 2/3 lib: Add generic boolean expression parser and eval
In reply to Richard PalethorpeHi!
Quoted 35 lines
Quoted 35 lines
lib/tst_bool_expr.c new file +29
-0@@ -0,0 +1,504 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* +* Copyright (c) 2020 Cyril Hrubis <[email protected]> +*/ +/* +* Boolean expression is evaluated in three steps. +* +* First of all the string containing the expression is tokenized. +* +* Secondly the the expression is transformed to a postfix (RPN) notation by +* the shunting yard algorithm and the correctness of the expression is checked +* during the transformation as well. The fact that parenthesis are matched is +* asserted by the shunting yard algorithm itself while the rest is checked +* simply by checking if the preceding token is in a set of allowed tokens. +* This could be thought of as a simple open-coded state machine. +* +* An expression in the RPN form can be evaluated given a variable mapping +* function. The evaluation ignores most of errors because invalid expression +* will be rejected in the second step. +*/ + +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include "tst_bool_expr.h" + +#define MAX_TOK 1024 + +struct tok {
Quoted 8 lines
lib/tst_bool_expr.c line 31
Quoted 2 lines
lib/tst_bool_expr.c new file +2
-0+unsigned int pos; +char buf[MAX_TOK ];Instead we could save an index into the input string here and record the length. Then there is no need to copy the string or guess a suitable buffer length and we record the original token location for error reporting (although it seems you reconstruct the expression so it's not so useful).
I guess that this may be easier to work with, I will try to implement such changes.
Quoted 10 lines
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+enum tst_op char_to_op (char c) +{ +switch (c) { +case '(' : +return TST_OP_LPAR ; +case ')' : +return TST_OP_RPAR ; +case '&' : +return TST_OP_AND ; +case '|' :
Quoted 8 lines
lib/tst_bool_expr.c line 89
Quoted 5 lines
lib/tst_bool_expr.c new file +5
-0+return TST_OP_OR ; +case '!' : +return TST_OP_NOT ; +default : +return -1 ;This should probably be an enum value like
TST_OP_INVAL(still may be -1), otherwise it is likely to confuse static anlyses tools.
I tried to avoid adding more enum values since that means that we have to explicitly handle them in all switch () bodies. So I'm not sure what is worse, adding nop case to a few of these or having numeric value like that.
Quoted 166 lines
Quoted 153 lines
lib/tst_bool_expr.c new file +153
-0+ } +} + +static struct tst_expr *new_op (char c) +{ +struct tst_expr *ret; + + ret =malloc (sizeof (struct tst_expr )); +if (!ret) +return NULL ; + + ret->op =char_to_op (c); + ret->next =NULL ; + ret->err =NULL ; + +return ret; +} + +struct op_list { +struct tst_expr *first; +struct tst_expr *last; +unsigned int cnt; +}; + +static void op_list_append (struct op_list *list,struct tst_expr *val) +{ +if (!val) +return ; + +if (!list->first) + list->first = val; + +if (list->last) + list->last->next = val; + + list->last = val; + + list->cnt++; +} + +static void tokenize (const char *expr,struct op_list *ret) +{ +struct tok buf = {}; +size_t i; + +for (i =0 ; expr[i]; i++) { +switch (expr[i]) { +case '(' : +case ')' : +case '!' : +case '&' : +case '|' : +op_list_append (ret,new_var (tok_get (&buf))); +op_list_append (ret,new_op (expr[i])); +break ; +case '\t' : +case ' ' : +op_list_append (ret,new_var (tok_get (&buf))); +break ; +default : +tok_append (&buf, expr[i]); +break ; + } + } + +op_list_append (ret,new_var (tok_get (&buf))); +} + +void tst_bool_expr_print (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; + +for (i = expr; i; i = i->next) { +if (i->op !=TST_OP_VAR && prev_op) +fprintf (f," " ); + +switch (i->op) { +case TST_OP_AND : +fprintf (f,"&" ); +break ; +case TST_OP_OR : +fprintf (f,"|" ); +break ; +case TST_OP_NOT : +fprintf (f,"!" ); +break ; +case TST_OP_LPAR : +fprintf (f,"(" ); +break ; +case TST_OP_RPAR : +fprintf (f,")" ); +break ; +case TST_OP_VAR : +fprintf (f," %s " , i->val); +break ; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } +} + +static void tst_bool_expr_err (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; +unsigned int spaces =0 ; + +fprintf (f,"\n" ); + +for (i = expr; i; i = i->next) { +if (i->err) +break ; + +if (i->op !=TST_OP_VAR && prev_op) + spaces++; + +switch (i->op) { +case TST_OP_VAR : + spaces +=2 +strlen (i->val); +break ; +default : + spaces++; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } + +while (spaces--) +putc (' ' , f); + +fprintf (f,"^\n" ); +fprintf (f,"%s\n" , i->err); +} + +static inline void stack_push (struct tst_expr *stack[],unsigned int *stack_pos, +struct tst_expr *op) +{ + stack[(*stack_pos)++] = op; +} + +static inline int stack_empty (unsigned int stack_pos) +{ +return stack_pos ==0 ; +} + +static inline struct tst_expr *stack_pop(struct tst_expr *stack[],lib/tst_bool_expr.c line 252
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+ unsigned int *stack_pos) +{ +if (stack_empty (*stack_pos)) +return NULL ; + +return stack[--(*stack_pos)]; +} + +static inline enum tst_op stack_top_op (struct tst_expr *stack[], +unsigned int stack_pos)Just a nit, but usually this is called peek, right?
Quoted 1 line
As we are peeking at the top/next entry without removing it.
I guess that stack_peek_op() may be better name, it has to have the _op there since we dereference.
Quoted 11 lines
lib/tst_bool_expr.c line 258
Quoted 6 lines
lib/tst_bool_expr.c new file +6
-0+{ +if (stack_empty (stack_pos)) +return -1 ; + +return stack[stack_pos -1 ]->op; +}Perhaps we should copy & paste the dynamic preallocated vector we created for gfxprim? We are doing a bunch of mallocs and reinventing linked lists and stacks, which can all be represented by the vector IIRC.
I do not think that it would work for the tokenizer/RPN since we reorder that and free things from the middle vector is not ideal data structure for that, link list is better suited for that work. And as for the stack we use, these have nice upper bound on size so we do not really need dynamic array for that.
Quoted 10 lines
lib/tst_bool_expr.c line 266
Quoted 8 lines
lib/tst_bool_expr.c new file +8
-0+ +/* +* This is a complete list of which tokens can happen before any of: +* - variable +* - left parentesis +* - negation +* +* The -1 represents start of the expression. Then it should have an entry in the enum.
Same here, if we do that we will end up with nop cases in a few switches to avoid warnings.
Quoted 4 lines
lib/tst_bool_expr.c line 268
Quoted 2 lines
lib/tst_bool_expr.c new file +2
-0+*/ +static inline int check_one (int op)I guess there is no good name for this xD
As far as I can tell no there isn't :-).
Quoted 36 lines
Quoted 24 lines
lib/tst_bool_expr.c new file +24
-0+{ +switch (op) { +case TST_OP_AND : +case TST_OP_OR : +case TST_OP_NOT : +case -1 : +case TST_OP_LPAR : +return 0 ; +default : +return 1 ; + } +} + +/* +* And this checks for tokens that can happen before any of: +* - right parentesis +* - and +* - or +* +* This is also used to check that the last token in expression is correct one. +*/ +static inline int check_two (int op) +{ +switch (op) {lib/tst_bool_expr.c line 302
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case TST_OP_VAR : +case TST_OP_RPAR : +return 1 ; +default : +return 0 ; + } +} + +static struct tst_expr *shunting_yard (struct op_list *list) +{/* Translator stack */
Quoted 2 lines
lib/tst_bool_expr.c line 304
Quoted 2 lines
lib/tst_bool_expr.c new file +2
-0+struct tst_expr *stack[list->cnt]; +unsigned int stack_pos =0 ;
Or we can reame this to op_stack[]; I prefer naming variables reasonably.
Quoted 7 lines
lib/tst_bool_expr.c line 308
Quoted 4 lines
lib/tst_bool_expr.c new file +4
-0+struct tst_expr *out[list->cnt +1 ]; +unsigned int out_pos =0 ; +struct tst_expr *pars[list->cnt]; +unsigned int pars_pos =0 ;It seems we just push stuff to this stack then free everything at the end?
Yes, since we eliminate parentesis during the RPN transformation but we have to free the allocated memory at the end.
Quoted 21 lines
lib/tst_bool_expr.c line 311
Quoted 3 lines
lib/tst_bool_expr.c new file +3
-0+struct tst_expr *i; +unsigned int j; +int prev_op =-1 ;enum
tst_opprev_op=TST_OP_START;lib/tst_bool_expr.c line 323
Quoted 12 lines
lib/tst_bool_expr.c new file +12
-0+ +for (i = list->first; i; i = i->next) { +switch (i->op) { +case TST_OP_VAR : +if (check_one (prev_op) && prev_op !=TST_OP_LPAR ) { + i->err ="Expected operation" ; + goto err; + } + +stack_push (out, &out_pos, i); + +/* pop all negations */ Clearly :-)
Quoted 1 line
This is not the hardest thing to understand here!
I guess so, will remove the comment.
Are there any places in the code that are not commented and should be?
Quoted 64 lines
Quoted 46 lines
lib/tst_bool_expr.c new file +46
-0+while (stack_top_op (stack, stack_pos) ==TST_OP_NOT ) +stack_push (out, &out_pos,stack_pop (stack, &stack_pos)); +break ; +case TST_OP_LPAR : +if (check_one (prev_op)) { + i->err ="Expected operation" ; + goto err; + } + +stack_push (stack, &stack_pos, i); +break ; +case TST_OP_RPAR : +if (!check_two (prev_op)) { + i->err ="Expected variable or )" ; + goto err; + } + +stack_push (pars, &pars_pos, i); + +/* pop everything till ( */ +for (;;) { +struct tst_expr *op =stack_pop (stack, &stack_pos); + +if (!op) { + i->err ="Missing (" ; + goto err; + } + +if (op->op ==TST_OP_LPAR ) { +stack_push (pars, &pars_pos, op); +break ; + } + +stack_push (out, &out_pos, op); + } + +/* pop all negations */ +while (stack_top_op (stack, stack_pos) ==TST_OP_NOT ) +stack_push (out, &out_pos,stack_pop (stack, &stack_pos)); +break ; +case TST_OP_NOT : +if (check_one (prev_op)) { + i->err ="Expected operation" ; + goto err; + } +stack_push (stack, &stack_pos, i);lib/tst_bool_expr.c line 379
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+break ; +case TST_OP_AND : +case TST_OP_OR : +if (!check_two (prev_op)) { + i->err ="Expected variable or (" ; + goto err; + } + +/* pop all binary ops */ +for (;;) {It seems that we can only have at most one previous binary op (i.e. '&' or '|') on the stack before '(' or NULL. Any additional ops after '(' or NULL are removed.
So the loop can be limited to two iterations and we can assert it never reaches a third.
Quoted 14 lines
lib/tst_bool_expr.c line 389
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+enum tst_op top_op; + +if (stack_empty (stack_pos)) +break ; + + top_op =stack_top_op (stack, stack_pos); + +if (top_op ==TST_OP_LPAR || + top_op ==TST_OP_NOT ) +break ;'!'s are removed directly after a variable is seen or a '(' is removed. So it should be an error to find one on the stack at this point.
I will have a closer look at this two tomorrow, it's quite late in the evening for me now.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH 2/3 lib: Add generic boolean expression parser and eval
Hello,
Quoted 20 lines · Cyril Hrubis
Quoted 11 lines
Quoted 11 lines
lib/tst_bool_expr.c new file +10
-0+enum tst_op char_to_op (char c) +{ +switch (c) { +case '(' : +return TST_OP_LPAR ; +case ')' : +return TST_OP_RPAR ; +case '&' : +return TST_OP_AND ; +case '|' :Quoted 8 lines
lib/tst_bool_expr.c line 89
Quoted 5 lines
lib/tst_bool_expr.c new file +5
-0+return TST_OP_OR ; +case '!' : +return TST_OP_NOT ; +default : +return -1 ;This should probably be an enum value like
TST_OP_INVAL(still may be -1), otherwise it is likely to confuse static anlyses tools.
Quoted 4 lines
I tried to avoid adding more enum values since that means that we have to explicitly handle them in all switch () bodies. So I'm not sure what is worse, adding nop case to a few of these or having numeric value like that.
I think it is usually enough to have a 'default' in the switch statement to prevent warnings about unhandled values?
Of course there is still a tradeoff here, because you end up with an enum containing unrelated values.
Quoted 167 lines
Quoted 167 lines
Quoted 154 lines
lib/tst_bool_expr.c new file +153
-0+ } +} + +static struct tst_expr *new_op (char c) +{ +struct tst_expr *ret; + + ret =malloc (sizeof (struct tst_expr )); +if (!ret) +return NULL ; + + ret->op =char_to_op (c); + ret->next =NULL ; + ret->err =NULL ; + +return ret; +} + +struct op_list { +struct tst_expr *first; +struct tst_expr *last; +unsigned int cnt; +}; + +static void op_list_append (struct op_list *list,struct tst_expr *val) +{ +if (!val) +return ; + +if (!list->first) + list->first = val; + +if (list->last) + list->last->next = val; + + list->last = val; + + list->cnt++; +} + +static void tokenize (const char *expr,struct op_list *ret) +{ +struct tok buf = {}; +size_t i; + +for (i =0 ; expr[i]; i++) { +switch (expr[i]) { +case '(' : +case ')' : +case '!' : +case '&' : +case '|' : +op_list_append (ret,new_var (tok_get (&buf))); +op_list_append (ret,new_op (expr[i])); +break ; +case '\t' : +case ' ' : +op_list_append (ret,new_var (tok_get (&buf))); +break ; +default : +tok_append (&buf, expr[i]); +break ; + } + } + +op_list_append (ret,new_var (tok_get (&buf))); +} + +void tst_bool_expr_print (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; + +for (i = expr; i; i = i->next) { +if (i->op !=TST_OP_VAR && prev_op) +fprintf (f," " ); + +switch (i->op) { +case TST_OP_AND : +fprintf (f,"&" ); +break ; +case TST_OP_OR : +fprintf (f,"|" ); +break ; +case TST_OP_NOT : +fprintf (f,"!" ); +break ; +case TST_OP_LPAR : +fprintf (f,"(" ); +break ; +case TST_OP_RPAR : +fprintf (f,")" ); +break ; +case TST_OP_VAR : +fprintf (f," %s " , i->val); +break ; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } +} + +static void tst_bool_expr_err (FILE *f,struct tst_expr *expr) +{ +struct tst_expr *i; +int prev_op =0 ; +unsigned int spaces =0 ; + +fprintf (f,"\n" ); + +for (i = expr; i; i = i->next) { +if (i->err) +break ; + +if (i->op !=TST_OP_VAR && prev_op) + spaces++; + +switch (i->op) { +case TST_OP_VAR : + spaces +=2 +strlen (i->val); +break ; +default : + spaces++; + } + +if (i->op ==TST_OP_VAR ) + prev_op =0 ; +else + prev_op =1 ; + } + +while (spaces--) +putc (' ' , f); + +fprintf (f,"^\n" ); +fprintf (f,"%s\n" , i->err); +} + +static inline void stack_push (struct tst_expr *stack[],unsigned int *stack_pos, +struct tst_expr *op) +{ + stack[(*stack_pos)++] = op; +} + +static inline int stack_empty (unsigned int stack_pos) +{ +return stack_pos ==0 ; +} + +static inline struct tst_expr *stack_pop(struct tst_expr *stack[],lib/tst_bool_expr.c line 252
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+ unsigned int *stack_pos) +{ +if (stack_empty (*stack_pos)) +return NULL ; + +return stack[--(*stack_pos)]; +} + +static inline enum tst_op stack_top_op (struct tst_expr *stack[], +unsigned int stack_pos)Just a nit, but usually this is called peek, right?
Quoted 4 lines
Quoted 1 line
As we are peeking at the top/next entry without removing it.
I guess that
stack_peek_op()may be better name, it has to have the_opthere since we dereference.
+1
Quoted 13 lines
Quoted 12 lines
lib/tst_bool_expr.c line 258
Quoted 7 lines
lib/tst_bool_expr.c new file +6
-0+{ +if (stack_empty (stack_pos)) +return -1 ; + +return stack[stack_pos -1 ]->op; +}Perhaps we should copy & paste the dynamic preallocated vector we created for gfxprim? We are doing a bunch of mallocs and reinventing linked lists and stacks, which can all be represented by the vector IIRC.
Quoted 5 lines
I do not think that it would work for the tokenizer/RPN since we reorder that and free things from the middle vector is not ideal data structure for that, link list is better suited for that work. And as for the stack we use, these have nice upper bound on size so we do not really need dynamic array for that.
Well it is not really about needing it just for this, I'm more thinking about deduplicating array, stack and list code in general. However I guess this can be dealt with separately.
Quoted 96 lines
Quoted 11 lines
lib/tst_bool_expr.c line 266
Quoted 9 lines
lib/tst_bool_expr.c new file +8
-0+ +/* +* This is a complete list of which tokens can happen before any of: +* - variable +* - left parentesis +* - negation +* +* The -1 represents start of the expression. Then it should have an entry in the enum.
Same here, if we do that we will end up with nop cases in a few switches to avoid warnings.
Quoted 4 lines
Quoted 2 lines
+ */
+static inline intcheck_one(int op)I guess there is no good name for this xD
As far as I can tell no there isn't :-).
Quoted 36 lines
Quoted 24 lines
lib/tst_bool_expr.c new file +24
-0+{ +switch (op) { +case TST_OP_AND : +case TST_OP_OR : +case TST_OP_NOT : +case -1 : +case TST_OP_LPAR : +return 0 ; +default : +return 1 ; + } +} + +/* +* And this checks for tokens that can happen before any of: +* - right parentesis +* - and +* - or +* +* This is also used to check that the last token in expression is correct one. +*/ +static inline int check_two (int op) +{ +switch (op) {lib/tst_bool_expr.c line 302
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case TST_OP_VAR : +case TST_OP_RPAR : +return 1 ; +default : +return 0 ; + } +} + +static struct tst_expr *shunting_yard (struct op_list *list) +{/* Translator stack */Quoted 2 lines
lib/tst_bool_expr.c line 304
Quoted 2 lines
lib/tst_bool_expr.c new file +2
-0+struct tst_expr *stack[list->cnt]; +unsigned int stack_pos =0 ;Or we can reame this to op_stack[]; I prefer naming variables reasonably.
Quoted 7 lines
lib/tst_bool_expr.c line 308
Quoted 4 lines
lib/tst_bool_expr.c new file +4
-0+struct tst_expr *out[list->cnt +1 ]; +unsigned int out_pos =0 ; +struct tst_expr *pars[list->cnt]; +unsigned int pars_pos =0 ;It seems we just push stuff to this stack then free everything at the end?
Yes, since we eliminate parentesis during the RPN transformation but we have to free the allocated memory at the end.
Quoted 21 lines
lib/tst_bool_expr.c line 311
Quoted 3 lines
lib/tst_bool_expr.c new file +3
-0+struct tst_expr *i; +unsigned int j; +int prev_op =-1 ;enum
tst_opprev_op=TST_OP_START;lib/tst_bool_expr.c line 323
Quoted 12 lines
lib/tst_bool_expr.c new file +12
-0+ +for (i = list->first; i; i = i->next) { +switch (i->op) { +case TST_OP_VAR : +if (check_one (prev_op) && prev_op !=TST_OP_LPAR ) { + i->err ="Expected operation" ; + goto err; + } + +stack_push (out, &out_pos, i); + +/* pop all negations */ Clearly :-)
Quoted 5 lines
Quoted 1 line
This is not the hardest thing to understand here!
I guess so, will remove the comment.
Are there any places in the code that are not commented and should be?
I don't think so, unless you have references/links which you think would be particularly useful for understanding this implementation of the algorithm?
Signature · 2 lines
Thank you, Richard.
PATCH 2/3 lib: Add generic boolean expression parser and eval
Hi!
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 5 lines
lib/tst_bool_expr.c new file +5
-0+enum tst_op char_to_op (char c) +{ +switch (c) { +case '(' : +return TST_OP_LPAR ;lib/tst_bool_expr.c line 89
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case ')' : +return TST_OP_RPAR ; +case '&' : +return TST_OP_AND ; +case '|' : +return TST_OP_OR ; +case '!' : +return TST_OP_NOT ; +default : +return -1 ;This should probably be an enum value like
TST_OP_INVAL(still may be -1), otherwise it is likely to confuse static anlyses tools.
Quoted 7 lines
Quoted 4 lines
I tried to avoid adding more enum values since that means that we have to explicitly handle them in all switch () bodies. So I'm not sure what is worse, adding nop case to a few of these or having numeric value like that.
I think it is usually enough to have a 'default' in the switch statement to prevent warnings about unhandled values?
That is IMHO wrong as well since this solution defeats the purpose of the warning in the first place. I do actually like that warning since it tells me that I have forgotten something.
Quoted 2 lines
Of course there is still a tradeoff here, because you end up with an enum containing unrelated values.
And loose the warning as well.
Quoted 18 lines
Quoted 12 lines
Quoted 11 lines
lib/tst_bool_expr.c line 258
Quoted 6 lines
lib/tst_bool_expr.c new file +6
-0+{ +if (stack_empty (stack_pos)) +return -1 ; + +return stack[stack_pos -1 ]->op; +}Perhaps we should copy & paste the dynamic preallocated vector we created for gfxprim? We are doing a bunch of mallocs and reinventing linked lists and stacks, which can all be represented by the vector IIRC.
Quoted 5 lines
I do not think that it would work for the tokenizer/RPN since we reorder that and free things from the middle vector is not ideal data structure for that, link list is better suited for that work. And as for the stack we use, these have nice upper bound on size so we do not really need dynamic array for that.
Quoted 3 lines
Well it is not really about needing it just for this, I'm more thinking about deduplicating array, stack and list code in general. However I guess this can be dealt with separately.
Actually I think that with the token with indexes I can simplify the code even further and get rid of some.
Thanks for the review I will send a v2 later on.
Signature · 2 lines
Cyril Hrubis [email protected]
PATCH 2/3 lib: Add generic boolean expression parser and eval
Hi,
Quoted 28 lines · Cyril Hrubis
Hi!
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 5 lines
lib/tst_bool_expr.c new file +5
-0+enum tst_op char_to_op (char c) +{ +switch (c) { +case '(' : +return TST_OP_LPAR ;lib/tst_bool_expr.c line 89
Quoted 10 lines
lib/tst_bool_expr.c new file +10
-0+case ')' : +return TST_OP_RPAR ; +case '&' : +return TST_OP_AND ; +case '|' : +return TST_OP_OR ; +case '!' : +return TST_OP_NOT ; +default : +return -1 ;This should probably be an enum value like
TST_OP_INVAL(still may be -1), otherwise it is likely to confuse static anlyses tools.Quoted 7 lines
Quoted 4 lines
I tried to avoid adding more enum values since that means that we have to explicitly handle them in all switch () bodies. So I'm not sure what is worse, adding nop case to a few of these or having numeric value like that.
I think it is usually enough to have a 'default' in the switch statement to prevent warnings about unhandled values?
Quoted 8 lines
That is IMHO wrong as well since this solution defeats the purpose of the warning in the first place. I do actually like that warning since it tells me that I have forgotten something.
Quoted 2 lines
Of course there is still a tradeoff here, because you end up with an enum containing unrelated values.
And loose the warning as well.
This makes sense, but the function still says it returns enum tst_op, but actually also returns -1. Ideally the function would return a union of two enums, but I guess C doesn't allow that. At any rate I think you are correct here. Hopefully at some point I will have chance to try some more static analyses of LTP.
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 12 lines
lib/tst_bool_expr.c line 258
Quoted 7 lines
lib/tst_bool_expr.c new file +6
-0+{ +if (stack_empty (stack_pos)) +return -1 ; + +return stack[stack_pos -1 ]->op; +}Perhaps we should copy & paste the dynamic preallocated vector we created for gfxprim? We are doing a bunch of mallocs and reinventing linked lists and stacks, which can all be represented by the vector IIRC.
I do not think that it would work for the tokenizer/RPN since we reorder that and free things from the middle vector is not ideal data structure for that, link list is better suited for that work. And as for the stack we use, these have nice upper bound on size so we do not really need dynamic array for that.
Quoted 8 lines
Quoted 3 lines
Well it is not really about needing it just for this, I'm more thinking about deduplicating array, stack and list code in general. However I guess this can be dealt with separately.
Actually I think that with the token with indexes I can simplify the code even further and get rid of some.
Thanks for the review I will send a v2 later on.
+1
Signature · 2 lines
Thank you, Richard.
PATCH 3/3 lib/tst_kconfig: Make use of boolean expression eval
In reply to Cyril HrubisNow each string in the kconfig[] array in tst_test structure is an boolean expression which is evaluated. All expressions has to be true in order for the test to continue.
+ Update the docs.
--- doc/test-writing-guidelines.txt | 21 ++-- lib/newlib_tests/test_kconfig.c | 1 + lib/tst_kconfig.c | 186 ++++++++++++++++++++++++-------- 3 files changed, 154 insertions(+), 54 deletions(-)
doc/test-writing-guidelines.txt +13 -8
@@ -1643,21 +1643,26 @@ on the system, disabled syscalls can be detected by checking for 'ENOSYS' errno etc. However in rare cases core kernel features couldn't be detected based on the -kernel userspace API and we have to resort to kernel .config parsing. +kernel userspace API and we have to resort to parse the kernel .config. -For this cases the test should set the 'NULL' terminated '.needs_kconfigs' array -of kernel config options required for the test. The config option can be -specified either as plain "CONFIG_FOO" in which case it's sufficient for the -test continue if it's set to any value (typically =y or =m). Or with a value -as "CONFIG_FOO=bar" in which case the value has to match as well. The test is -aborted with 'TCONF' if any of the required options were not set. +For this cases the test should set the 'NULL' terminated '.needs_kconfigs' +array of boolean expressions with constraints on the kconfig variables. The +boolean expression consits of variables, two binary operations '&' and '|', +negation '!' and correct sequence of parentesis '()'. Variables are expected +to be in a form of "CONFIG_FOO[=bar]". + +The test will continue to run if all expressions are evaluated to 'True'. +Missing variable is mapped to 'False' as well as variable with different than +specified value, e.g. 'CONFIG_FOO=bar' will evaluate to 'False' if the value +is anything else but 'bar'. If config variable is specified as plain +'CONFIG_FOO' it's evaluated to true it's set to any value (typically =y or =m). [source,c] ------------------------------------------------------------------------------- #include "tst_test.h" static const char *kconfigs[] = { - "CONFIG_X86_INTEL_UMIP", + "CONFIG_X86_INTEL_UMIP | CONFIG_X86_UMIP", NULL };
lib/newlib_tests/test_kconfig.c +1 -0
@@ -14,6 +14,7 @@ static const char *kconfigs[] = {"CONFIG_MMU" ,"CONFIG_EXT4_FS=m" ,"CONFIG_PGTABLE_LEVELS=4" , +"CONFIG_MMU & CONFIG_EXT4_FS=m" , NULL };
lib/tst_kconfig.c +140 -46
232 lines not on this page · raw message
Signature · 1 line
2.26.2
PATCH 3/3 lib/tst_kconfig: Make use of boolean expression eval
Hello,
I don't see anything obviously wrong here, just some nits.
Quoted 93 lines · Cyril Hrubis
Now each string in the kconfig[] array in
tst_teststructure is an boolean expression which is evaluated. All expressions has to be true in order for the test to continue.+ Update the docs.
Signed-off-by Cyril Hrubis <[email protected]>CC Pengfei Xu <[email protected]>--- doc/test-writing-guidelines.txt | 21 ++-- lib/newlib_tests/test_kconfig.c | 1 + lib/tst_kconfig.c | 186 ++++++++++++++++++++++++-------- 3 files changed, 154 insertions(+), 54 deletions(-)doc/test-writing-guidelines.txt +13
-8@@ -1643,21 +1643,26 @@ on the system, disabled syscalls can be detected by checking for 'ENOSYS' errno etc. However in rare cases core kernel features couldn't be detected based on the -kernel userspace API and we have to resort to kernel .config parsing. +kernel userspace API and we have to resort to parse the kernel .config. -For this cases the test should set the 'NULL' terminated '.needs_kconfigs' array -of kernel config options required for the test. The config option can be -specified either as plain "CONFIG_FOO" in which case it's sufficient for the -test continue if it's set to any value (typically =y or =m). Or with a value -as "CONFIG_FOO=bar" in which case the value has to match as well. The test is -aborted with 'TCONF' if any of the required options were not set. +For this cases the test should set the 'NULL' terminated '.needs_kconfigs' +array of boolean expressions with constraints on the kconfig variables. The +boolean expression consits of variables, two binary operations '&' and '|', +negation '!' and correct sequence of parentesis '()'. Variables are expected +to be in a form of "CONFIG_FOO[=bar]". + +The test will continue to run if all expressions are evaluated to 'True'. +Missing variable is mapped to 'False' as well as variable with different than +specified value, e.g. 'CONFIG_FOO=bar' will evaluate to 'False' if the value +is anything else but 'bar'. If config variable is specified as plain +'CONFIG_FOO' it's evaluated to true it's set to any value (typically =y or =m). [source,c] ------------------------------------------------------------------------------- #include "tst_test.h" static const char *kconfigs[] = { - "CONFIG_X86_INTEL_UMIP", + "CONFIG_X86_INTEL_UMIP | CONFIG_X86_UMIP", NULL };lib/newlib_tests/test_kconfig.c +1
-0@@ -14,6 +14,7 @@ static const char *kconfigs[] = {"CONFIG_MMU" ,"CONFIG_EXT4_FS=m" ,"CONFIG_PGTABLE_LEVELS=4" , +"CONFIG_MMU & CONFIG_EXT4_FS=m" , NULL };lib/tst_kconfig.c +3
-8@@ -12,6 +12,7 @@#define TST_NO_DEFAULT_MAIN #include "tst_test.h" #include "tst_kconfig.h" +#include "tst_bool_expr.h" static const char *kconfig_path (char *path_buf,size_t path_buf_len) {@@ -184,86 +185,179 @@ static size_t array_len(const char *const kconfigs[])return i; } -static int compare_res (struct tst_kconfig_var *var,const char *kconfig, -char choice,const char *val) +static inline unsigned int get_len (const char * kconfig) { -if (var->choice != choice) { -tst_res (TINFO ,"Needs kernel %s, have %c" , kconfig, var->choice); -return 1 ; - } +char *sep =index (kconfig,'=' ); -if (choice !='v' ) -return 0 ;
lib/tst_kconfig.c static size_t array_len(const char *const kconfigs[]) · line 198
Quoted 10 lines
lib/tst_kconfig.c +6
-3+if (!sep) +return strlen (kconfig); -if (strcmp (var->val, val)) { -tst_res (TINFO ,"Needs kernel %s, have %s" , kconfig, var->val); -return 1 ; +return sep - kconfig; +} + +static inline unsigned int get_var_cnt(struct tst_expr *exprs[],
const *?
Quoted 10 lines
lib/tst_kconfig.c +10
-0+ unsigned int expr_cnt) +{ +unsigned int i; +struct tst_expr *j; +unsigned int cnt =0 ; + +for (i =0 ; i < expr_cnt; i++) { +for (j = exprs[i]; j; j = j->next) { +if (j->op ==TST_OP_VAR ) + cnt++;
lib/tst_kconfig.c static size_t array_len(const char *const kconfigs[])
Quoted 10 lines
lib/tst_kconfig.c +3
-2+ } } -return 0 ; +return cnt; } -static inline unsigned int get_len (const char * kconfig) +static struct tst_kconfig_var *find_var(struct tst_kconfig_var vars[],
also const []?
Quoted 15 lines
lib/tst_kconfig.c +8
-4+unsigned int var_cnt, + const char *var) { -char *sep =index (kconfig,'=' ); + unsigned int i; -if (!sep) -return strlen (kconfig); +for (i =0 ; i < var_cnt; i++) { +if (!strcmp (vars[i].id, var)) +return &vars[i]; + } -return sep - kconfig; +return NULL ;
lib/tst_kconfig.c static size_t array_len(const char *const kconfigs[]) · line 235
Quoted 10 lines
lib/tst_kconfig.c +7
-1} -void tst_kconfig_check (const char *const kconfigs[]) +/* +* Fill in the kconfig variables array from the expressions. Also makes sure +* that each variable is copied to the array exaclty once. +*/ +static inline unsigned int get_vars (struct tst_expr *exprs[], +unsigned int expr_cnt, +struct tst_kconfig_var vars[])
get_vars sounds like a read-onlyl operation, maybe populate_vars or similar?
Quoted 67 lines
lib/tst_kconfig.c +44
-14{ -size_t vars_cnt =array_len (kconfigs); -struct tst_kconfig_var vars[vars_cnt];unsigned int i; -int abort_test =0 ; +struct tst_expr *j; +unsigned int cnt =0 ; + +for (i =0 ; i < expr_cnt; i++) { +for (j = exprs[i]; j; j = j->next) { +struct tst_kconfig_var *var; -memset (vars,0 ,sizeof (*vars) * vars_cnt); +if (j->op !=TST_OP_VAR ) +continue ; -for (i =0 ; i < vars_cnt; i++) { - vars[i].id_len =get_len (kconfigs[i]); + vars[cnt].id_len =get_len (j->val); -if (vars[i].id_len >=sizeof (vars[i].id)) -tst_brk (TBROK ,"kconfig var id too long!" ); +if (vars[cnt].id_len >=sizeof (vars[cnt].id)) +tst_brk (TBROK ,"kconfig var id too long!" ); -strncpy (vars[i].id, kconfigs[i], vars[i].id_len); +strncpy (vars[cnt].id, j->val, vars[cnt].id_len); + + var =find_var (vars, cnt, vars[cnt].id); + +if (var) + j->priv = var; +else + j->priv = &vars[cnt++]; + } } -tst_kconfig_read (vars, vars_cnt); +return cnt; +} + +static int map (struct tst_expr *expr) +{ +struct tst_kconfig_var *var = expr->priv; -for (i =0 ; i < vars_cnt; i++) { -if (vars[i].choice ==0 ) { -tst_res (TINFO ,"Missing kernel %s" , kconfigs[i]); - abort_test =1 ; +if (var->choice ==0 ) +return 0 ; + +const char *val =strchr (expr->val,'=' ); + +/* CONFIG_FOO evaluates to true if y or m */ +if (!val) +return var->choice =='y' || var->choice =='m' ; + +char choice ='v' ; + val++; + +if (!strcmp (val,"n" )) + choice ='n' ; + +if (!strcmp (val,"y" )) + choice ='y' ; +
lib/tst_kconfig.c static size_t array_len(const char *const kconfigs[]) · line 298
Quoted 10 lines
lib/tst_kconfig.c +10
-0+if (!strcmp (val,"m" )) + choice ='m' ; + +if (choice !='v' ) +return var->choice == choice; + +return !strcmp (val, var->val); +} + +static void dump_vars (struct tst_expr *expr)
const *?
Quoted 81 lines
lib/tst_kconfig.c +49
-14+{ +struct tst_expr *i; +struct tst_kconfig_var *var; + +tst_res (TINFO ,"Variables:" ); + +for (i = expr; i; i = i->next) { +if (i->op !=TST_OP_VAR ) +continue ; + + var = i->priv; + +if (!var->choice) { +tst_res (TINFO ,"%s Undefined" , var->id);continue ; } -if (vars[i].choice =='n' ) { -tst_res (TINFO ,"Kernel %s is not set" , kconfigs[i]); - abort_test =1 ; +if (var->choice =='v' ) { +tst_res (TINFO ,"%s = %s" , var->id, var->val);continue ; } -const char *val =strchr (kconfigs[i],'=' ); +tst_res (TINFO ,"%s = %c" , var->id, var->choice); + } +} -if (val) { -char choice ='v' ; - val++; +void tst_kconfig_check (const char *const kconfigs[]) +{ +size_t expr_cnt =array_len (kconfigs); +struct tst_expr *exprs[expr_cnt]; +unsigned int i, var_cnt; +int abort_test =0 ; + +for (i =0 ; i < expr_cnt; i++) { + exprs[i] =tst_bool_expr_parse (kconfigs[i]); + +if (!exprs[i]) +tst_brk (TBROK ,"Invalid kconfig expression!" ); + } -if (!strcmp (val,"y" )) - choice ='y' ; + var_cnt =get_var_cnt (exprs, expr_cnt); +struct tst_kconfig_var vars[var_cnt]; -if (!strcmp (val,"m" )) - choice ='m' ; + var_cnt =get_vars (exprs, expr_cnt, vars); -if (compare_res (&vars[i], kconfigs[i], choice, val)) - abort_test =1 ; +tst_kconfig_read (vars, var_cnt); +for (i =0 ; i < expr_cnt; i++) { +int val =tst_bool_expr_eval (exprs[i], map); + +if (val !=1 ) { + abort_test =1 ; +tst_res (TINFO ,"Expression '%s' not satisfied!" , kconfigs[i]); +dump_vars (exprs[i]); } -free (vars[i].val); +tst_bool_expr_free (exprs[i]); + } + +for (i =0 ; i < var_cnt; i++) { +if (vars[i].choice =='v' ) +free (vars[i].val); }if (
abort_test)Signature · 1 line
2.26.2
Signature · 2 lines
Thank you, Richard.