Changes between Version 21 and Version 22 of Specification/RSF2DIMACS


Ignore:
Timestamp:
Mar 10, 2015, 11:59:12 AM (10 years ago)
Author:
krafczy
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • Specification/RSF2DIMACS

    v21 v22  
    33[[PageOutline(2-5, Table of Contents, pullout)]] 
    44 
    5 == Translation of Tristate Variables == 
     5== Translation of Boolean and Tristate Variables == 
     6When evaluating KConfig each variable is assigned a value; possible values are: 
     7* 0: The variable is not selected (constant symbol: 'n') 
     8* 1: The variable is selected as a module (constant symbol: 'm') 
     9* 2: The variable is permanently selected (constant symbol: 'y') 
     10 
     11Boolean variables can only have the values 0 or 2. They are translated as a single boolean variable with their name. 
     12* In RSF: 
     13{{{ 
     14Item VARIABLE boolean 
     15}}} 
     16* Meaning: 
     17||'''VARIABLE'''||'''Explanation'''|| 
     18||0||VARIABLE is permanently deselected ('n' was selected)|| 
     19||1||VARIABLE is permanently selected ('y' was selected)|| 
     20 
    621Tristate variables will be translated into 2 variables. This translation shall be equal to the translation of Undertaker or KConfigReader: 
    722* One variable declaring whether the related KConfig variable is permanently selected 
    … …  
    2439||1||1||Illegal state|| 
    2540 
    26 == Translation of String, Integer, Hex Variables == 
    27 === Concrete Values === 
    28 For String, Integer, and Hex variables we list all used values as different variables in the following form: 
    29 {{{ 
    30 VARIABLE=<value> 
    31 }}} 
    32 For a not configured variable (or an empty String) a variable in the following form will be created: 
    33 {{{ 
    34 VARIABLE=n 
    35 }}} 
    36 Further, constraints must ensure that at most one variable will be selected: 
    37 * In DIMACS/Boolean formula: 
    38 {{{ 
    39 Not(VARIABLE=n) OR Not(VARIABLE=value1) 
    40 Not(VARIABLE=n) OR Not(VARIABLE=value2) 
    41 ... 
    42 Not(VARIABLE=n) OR Not(VARIABLE=valueN) 
    43 Not(VARIABLE=value1) OR Not(VARIABLE=value2) 
    44 ... 
    45 Not(VARIABLE=value1) OR Not(VARIABLE=valueN) 
    46 }}} 
    47 All combinations of 2 negated variables. 
    48 === Ranges === 
    49 Ranges of !Integers/Hex variables will not be considered. Since KConfig supports only == and != comparisons, only values used in constraints will be translated to DIMACS. 
     41== Translation of ''depends'' Constraints == 
     42A depends statement specifies the maximum possible selection for a variable. The constraint is evaluated in "integer logic", with "or" being "max", "and" being "min" and "not" being "2-". 
     43 
     44 * In RSF: 
     45{{{ 
     46depends Variable Condition 
     47}}} 
     48 
     49=== Variable is Boolean === 
     50 * In Boolean formula: 
     51{{{ 
     52Not(Condition) implies Not(Variable) 
     53}}} 
     54 * In DIMACS: 
     55{{{ 
     56Condition or Not(Variable) 
     57}}} 
     58 
     59If Condition contains tristate variables, then the version that decides whether they are permanently selected is used. This is because if the tristate is selected as a module, the value would be 1. Since depends specifies the maximum possible value for the variable, for boolean variables the only possible solution would be 0. 
     60 
     61If Condition contains variables that are neither boolean nor tristate (i.e. integer, hex, string or unknown) they are treated as false (i.e. 'n'). 
     62 
     63=== Variable is Tristate === 
     64 * In Boolean formula: 
     65{{{ 
     66Not(Condition) implies Not(Variable) 
     67Not(Condition) implies Not(Variable_MODULE) 
     68}}} 
     69 * In DIMACS: 
     70{{{ 
     71Condition or Not(Variable) 
     72Condition or Not(Variable_MODULE) 
     73}}} 
     74 
     75If Condition contains tristate variables, then the version that decides whether they are permanently selected is used when parsing the Condition for the first constraint. This is because the Condition must evaluate to 2 in "integer logic", when Variable is selected as 2. 
     76When parsing the Condition for the second constraint, (VAR or VAR_MODULE) is used for module variables. This is because the Condition must evaluate to 2 or 1, when Variable is selected as 1(since depends specifies the maximum possible selection). 
     77 
     78If Conditions contains 'm' (i.e. the constant symbol for "1"), it is treated as false for the first constraint and as true for the second constraint. Moreover, since the negation is handled as "2-" in "integer logic", NOT('m') equals 'm' (2-1 = 1). 
     79 
     80If Condition contains variables that are neither boolean nor tristate (i.e. integer, hex, string or unknown) they are treated as false (i.e. 'n'). 
     81 
     82== Translation of ''!ItemSelects'' Constraints == 
     83TODO: review 
     84The [https://www.kernel.org/doc/Documentation/kbuild/kconfig-language.txt KConfig specification] defines select statements as follows: 
     85> reverse dependencies: "select" <symbol> !["if" <expr>] 
     86>  While normal dependencies reduce the upper limit of a symbol (see 
     87>  below), reverse dependencies can be used to force a lower limit of 
     88>  another symbol. The value of the current menu symbol is used as the 
     89>  minimal value <symbol> can be set to. If <symbol> is selected multiple 
     90>  times, the limit is set to the largest selection. 
     91>  Reverse dependencies can only be used with boolean or tristate 
     92>  symbols. 
     931. Translation of Boolean !ItemSelect statements: 
     94 * In RSF: 
     95{{{ 
     96ItemSelects BOOLEAN_VAR OTHER_VAR CONDITION 
     97}}} 
     98 * In Boolean formula: 
     99{{{ 
     100(BOOLEAN_VAR and CONDITION) implies OTHER_VAR 
     101}}} 
     102 * In DIMACS: 
     103{{{ 
     104Not(BOOLEAN_VAR) or Not(CONDITION) or OTHER_VAR 
     105}}} 
     1062. Translation of Tristate !ItemSelect statements: 
     107 * In RSF: 
     108{{{ 
     109ItemSelects TRISTATE_VAR OTHER_VAR CONDITION 
     110}}} 
     111 * In Boolean formula: 
     112{{{ 
     113(TRISTATE_VAR and CONDITION) implies OTHER_VAR 
     114(TRISTATE_VAR_MODULE and CONDITION) implies OTHER_VAR_MODULE 
     115}}} 
     116 * In DIMACS: 
     117{{{ 
     118Not(TRISTATE_VAR) or Not(CONDITION) or OTHER_VAR 
     119Not(TRISTATE_VAR_MODULE) or Not(CONDITION) or OTHER_VAR_MODULE 
     120}}} 
    50121 
    51122== Translation of Choices == 
     123TODO: review 
    52124A choice can be treated as an Enumeration. The [https://www.kernel.org/doc/Documentation/kbuild/kconfig-language.txt KConfig specification] defines a choice as follows: 
    53125>choices: [[br]] 
    … …  
    109181 
    110182=== Translation of Tristate Choices === 
     183TODO: review 
    111184A Tristate Choice can be selected as permanently selected ('y') or as a module ('m'). 
    112185* If the Choice is permanently selected ('y'), exactly one of its !ChoiceItems must also be permanently selected ('y'). 
    … …  
    149222... 
    150223Not(CHOICE_MODULE) or Not(ItemN) 
    151 }}} 
    152  
    153 == Translation of ''depends'' Constraints == 
    154 Each variable can have multiple depends statements, specifying when the variable can be configured. The variable must remain unconfigured (in case of a Boolean or Tristate variable, it must be set to ''n''), if none of the depends statements is fulfilled. 
    155 Conditions will be translated as follows: 
    156 1. One Condition: 
    157  * In RSF: 
    158 {{{ 
    159 depends Variable Condition 
    160 }}} 
    161  * In Boolean formula: 
    162 {{{ 
    163 Not(Condition) implies Not(Variable) 
    164 }}} 
    165  * In DIMACS: 
    166 {{{ 
    167 Condition or Not(Variable) 
    168 }}} 
    169 1. Multiple Conditions 
    170  * In RSF: 
    171 {{{ 
    172 depends Variable Condition1 
    173 depends Variable Condition2 
    174 }}} 
    175  * In Boolean formula: 
    176 {{{ 
    177 Not(Condition1) and Not(Condition2) implies Not(Variable) 
    178 }}} 
    179  * In DIMACS: 
    180 {{{ 
    181 Condition1 or Condition2 or Not(Variable) 
    182 }}} 
    183 1. Variable depends of Tristate 
    184  * In RSF: 
    185 {{{ 
    186 depends VARIABLE TRISTATE_VAR 
    187 }}} 
    188  * In Boolean formula: 
    189 {{{ 
    190 Not(TRISTATE_VAR) and Not(TRISTATE_VAR_MODULE) implies Not(VARIABLE) 
    191 }}} 
    192  * In DIMACS: 
    193 {{{ 
    194 TRISTATE_VAR or TRISTATE_VAR_MODULE or Not(VARIABLE) 
    195 }}} 
    196 1. Tristate variable depends of Condition 
    197  * In RSF: 
    198 {{{ 
    199 depends TRISTATE_VAR CONDITION 
    200 }}} 
    201  * In Boolean formula: 
    202 {{{ 
    203 Not(CONDITION) implies Not(TRISTATE_VAR) 
    204 Not(CONDITION) implies Not(TRISTATE_VAR_MODULE) 
    205 }}} 
    206  * In DIMACS: 
    207 {{{ 
    208 CONDITION or Not(TRISTATE_VAR) 
    209 CONDITION or Not(TRISTATE_VAR_MODULE_VAR) 
    210 }}} 
    211  
    212 == Translation of ''!ItemSelects'' Constraints == 
    213 The [https://www.kernel.org/doc/Documentation/kbuild/kconfig-language.txt KConfig specification] defines select statements as follows: 
    214 > reverse dependencies: "select" <symbol> !["if" <expr>] 
    215 >  While normal dependencies reduce the upper limit of a symbol (see 
    216 >  below), reverse dependencies can be used to force a lower limit of 
    217 >  another symbol. The value of the current menu symbol is used as the 
    218 >  minimal value <symbol> can be set to. If <symbol> is selected multiple 
    219 >  times, the limit is set to the largest selection. 
    220 >  Reverse dependencies can only be used with boolean or tristate 
    221 >  symbols. 
    222 1. Translation of Boolean !ItemSelect statements: 
    223  * In RSF: 
    224 {{{ 
    225 ItemSelects BOOLEAN_VAR OTHER_VAR CONDITION 
    226 }}} 
    227  * In Boolean formula: 
    228 {{{ 
    229 (BOOLEAN_VAR and CONDITION) implies OTHER_VAR 
    230 }}} 
    231  * In DIMACS: 
    232 {{{ 
    233 Not(BOOLEAN_VAR) or Not(CONDITION) or OTHER_VAR 
    234 }}} 
    235 2. Translation of Tristate !ItemSelect statements: 
    236  * In RSF: 
    237 {{{ 
    238 ItemSelects TRISTATE_VAR OTHER_VAR CONDITION 
    239 }}} 
    240  * In Boolean formula: 
    241 {{{ 
    242 (TRISTATE_VAR and CONDITION) implies OTHER_VAR 
    243 (TRISTATE_VAR_MODULE and CONDITION) implies OTHER_VAR_MODULE 
    244 }}} 
    245  * In DIMACS: 
    246 {{{ 
    247 Not(TRISTATE_VAR) or Not(CONDITION) or OTHER_VAR 
    248 Not(TRISTATE_VAR_MODULE) or Not(CONDITION) or OTHER_VAR_MODULE 
    249224}}} 
    250225 
    … …  
    269244}}} 
    270245 
     246== Translation of String, Integer, Hex Variables == 
     247=== Concrete Values === 
     248For String, Integer, and Hex variables we list all used values as different variables in the following form: 
     249{{{ 
     250VARIABLE=<value> 
     251}}} 
     252For a not configured variable (or an empty String) a variable in the following form will be created: 
     253{{{ 
     254VARIABLE=n 
     255}}} 
     256Further, constraints must ensure that at most one variable will be selected: 
     257* In DIMACS/Boolean formula: 
     258{{{ 
     259Not(VARIABLE=n) OR Not(VARIABLE=value1) 
     260Not(VARIABLE=n) OR Not(VARIABLE=value2) 
     261... 
     262Not(VARIABLE=n) OR Not(VARIABLE=valueN) 
     263Not(VARIABLE=value1) OR Not(VARIABLE=value2) 
     264... 
     265Not(VARIABLE=value1) OR Not(VARIABLE=valueN) 
     266}}} 
     267All combinations of 2 negated variables. 
     268=== Ranges === 
     269Ranges of !Integers/Hex variables will not be considered. Since KConfig supports only == and != comparisons, only values used in constraints will be translated to DIMACS. 
     270 
    271271== Unused Variables == 
    272272If a variable is not used, this variable must be deselected (selection 'n'). A variable is not used if there exist a condition where the variable is not visible, has no prompt, and will not be selected by another variable.[[BR]]