scripts/kconfig/symbol.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2002 Roman Zippel <[email protected]>
   4  */
   5
   6 #include <sys/types.h>
   7 #include <ctype.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <regex.h>
  11
  12 #include "internal.h"
  13 #include "lkc.h"
  14
  15 struct symbol symbol_yes = {
  16         .name = "y",
  17         .type = S_TRISTATE,
  18         .curr = { "y", yes },
  19         .menus = LIST_HEAD_INIT(symbol_yes.menus),
  20         .flags = SYMBOL_CONST|SYMBOL_VALID,
  21 };
  22
  23 struct symbol symbol_mod = {
  24         .name = "m",
  25         .type = S_TRISTATE,
  26         .curr = { "m", mod },
  27         .menus = LIST_HEAD_INIT(symbol_mod.menus),
  28         .flags = SYMBOL_CONST|SYMBOL_VALID,
  29 };
  30
  31 struct symbol symbol_no = {
  32         .name = "n",
  33         .type = S_TRISTATE,
  34         .curr = { "n", no },
  35         .menus = LIST_HEAD_INIT(symbol_no.menus),
  36         .flags = SYMBOL_CONST|SYMBOL_VALID,
  37 };
  38
  39 struct symbol *modules_sym;
  40 static tristate modules_val;
  41 static int sym_warnings;
  42
  43 enum symbol_type sym_get_type(const struct symbol *sym)
  44 {
  45         enum symbol_type type = sym->type;
  46
  47         if (type == S_TRISTATE && modules_val == no)
  48                 type = S_BOOLEAN;
  49         return type;
  50 }
  51
  52 const char *sym_type_name(enum symbol_type type)
  53 {
  54         switch (type) {
  55         case S_BOOLEAN:
  56                 return "bool";
  57         case S_TRISTATE:
  58                 return "tristate";
  59         case S_INT:
  60                 return "integer";
  61         case S_HEX:
  62                 return "hex";
  63         case S_STRING:
  64                 return "string";
  65         case S_UNKNOWN:
  66                 return "unknown";
  67         }
  68         return "???";
  69 }
  70
  71 /**
  72  * sym_get_choice_menu - get the parent choice menu if present
  73  *
  74  * @sym: a symbol pointer
  75  *
  76  * Return: a choice menu if this function is called against a choice member.
  77  */
  78 struct menu *sym_get_choice_menu(const struct symbol *sym)
  79 {
  80         struct menu *menu = NULL;
  81         struct menu *m;
  82
  83         /*
  84          * Choice members must have a prompt. Find a menu entry with a prompt,
  85          * and assume it resides inside a choice block.
  86          */
  87         list_for_each_entry(m, &sym->menus, link)
  88                 if (m->prompt) {
  89                         menu = m;
  90                         break;
  91                 }
  92
  93         if (!menu)
  94                 return NULL;
  95
  96         do {
  97                 menu = menu->parent;
  98         } while (menu && !menu->sym);
  99
 100         if (menu && menu->sym && sym_is_choice(menu->sym))
 101                 return menu;
 102
 103         return NULL;
 104 }
 105
 106 static struct property *sym_get_default_prop(struct symbol *sym)
 107 {
 108         struct property *prop;
 109
 110         for_all_defaults(sym, prop) {
 111                 prop->visible.tri = expr_calc_value(prop->visible.expr);
 112                 if (prop->visible.tri != no)
 113                         return prop;
 114         }
 115         return NULL;
 116 }
 117
 118 struct property *sym_get_range_prop(struct symbol *sym)
 119 {
 120         struct property *prop;
 121
 122         for_all_properties(sym, prop, P_RANGE) {
 123                 prop->visible.tri = expr_calc_value(prop->visible.expr);
 124                 if (prop->visible.tri != no)
 125                         return prop;
 126         }
 127         return NULL;
 128 }
 129
 130 static long long sym_get_range_val(struct symbol *sym, int base)
 131 {
 132         sym_calc_value(sym);
 133         switch (sym->type) {
 134         case S_INT:
 135                 base = 10;
 136                 break;
 137         case S_HEX:
 138                 base = 16;
 139                 break;
 140         default:
 141                 break;
 142         }
 143         return strtoll(sym->curr.val, NULL, base);
 144 }
 145
 146 static void sym_validate_range(struct symbol *sym)
 147 {
 148         struct property *prop;
 149         struct symbol *range_sym;
 150         int base;
 151         long long val, val2;
 152
 153         switch (sym->type) {
 154         case S_INT:
 155                 base = 10;
 156                 break;
 157         case S_HEX:
 158                 base = 16;
 159                 break;
 160         default:
 161                 return;
 162         }
 163         prop = sym_get_range_prop(sym);
 164         if (!prop)
 165                 return;
 166         val = strtoll(sym->curr.val, NULL, base);
 167         range_sym = prop->expr->left.sym;
 168         val2 = sym_get_range_val(range_sym, base);
 169         if (val >= val2) {
 170                 range_sym = prop->expr->right.sym;
 171                 val2 = sym_get_range_val(range_sym, base);
 172                 if (val <= val2)
 173                         return;
 174         }
 175         sym->curr.val = range_sym->curr.val;
 176 }
 177
 178 static void sym_set_changed(struct symbol *sym)
 179 {
 180         struct menu *menu;
 181
 182         list_for_each_entry(menu, &sym->menus, link)
 183                 menu->flags |= MENU_CHANGED;
 184 }
 185
 186 static void sym_set_all_changed(void)
 187 {
 188         struct symbol *sym;
 189
 190         for_all_symbols(sym)
 191                 sym_set_changed(sym);
 192 }
 193
 194 static void sym_calc_visibility(struct symbol *sym)
 195 {
 196         struct property *prop;
 197         tristate tri;
 198
 199         /* any prompt visible? */
 200         tri = no;
 201         for_all_prompts(sym, prop) {
 202                 prop->visible.tri = expr_calc_value(prop->visible.expr);
 203                 tri = EXPR_OR(tri, prop->visible.tri);
 204         }
 205         if (tri == mod && (sym->type != S_TRISTATE || modules_val == no))
 206                 tri = yes;
 207         if (sym->visible != tri) {
 208                 sym->visible = tri;
 209                 sym_set_changed(sym);
 210         }
 211         if (sym_is_choice_value(sym))
 212                 return;
 213         /* defaulting to "yes" if no explicit "depends on" are given */
 214         tri = yes;
 215         if (sym->dir_dep.expr)
 216                 tri = expr_calc_value(sym->dir_dep.expr);
 217         if (tri == mod && sym_get_type(sym) == S_BOOLEAN)
 218                 tri = yes;
 219         if (sym->dir_dep.tri != tri) {
 220                 sym->dir_dep.tri = tri;
 221                 sym_set_changed(sym);
 222         }
 223         tri = no;
 224         if (sym->rev_dep.expr)
 225                 tri = expr_calc_value(sym->rev_dep.expr);
 226         if (tri == mod && sym_get_type(sym) == S_BOOLEAN)
 227                 tri = yes;
 228         if (sym->rev_dep.tri != tri) {
 229                 sym->rev_dep.tri = tri;
 230                 sym_set_changed(sym);
 231         }
 232         tri = no;
 233         if (sym->implied.expr)
 234                 tri = expr_calc_value(sym->implied.expr);
 235         if (tri == mod && sym_get_type(sym) == S_BOOLEAN)
 236                 tri = yes;
 237         if (sym->implied.tri != tri) {
 238                 sym->implied.tri = tri;
 239                 sym_set_changed(sym);
 240         }
 241 }
 242
 243 /*
 244  * Find the default symbol for a choice.
 245  * First try the default values for the choice symbol
 246  * Next locate the first visible choice value
 247  * Return NULL if none was found
 248  */
 249 struct symbol *sym_choice_default(struct menu *choice)
 250 {
 251         struct menu *menu;
 252         struct symbol *def_sym;
 253         struct property *prop;
 254
 255         /* any of the defaults visible? */
 256         for_all_defaults(choice->sym, prop) {
 257                 prop->visible.tri = expr_calc_value(prop->visible.expr);
 258                 if (prop->visible.tri == no)
 259                         continue;
 260                 def_sym = prop_get_symbol(prop);
 261                 if (def_sym->visible != no)
 262                         return def_sym;
 263         }
 264
 265         /* just get the first visible value */
 266         menu_for_each_sub_entry(menu, choice)
 267                 if (menu->sym && menu->sym->visible != no)
 268                         return menu->sym;
 269
 270         /* failed to locate any defaults */
 271         return NULL;
 272 }
 273
 274 /*
 275  * sym_calc_choice - calculate symbol values in a choice
 276  *
 277  * @choice: a menu of the choice
 278  *
 279  * Return: a chosen symbol
 280  */
 281 struct symbol *sym_calc_choice(struct menu *choice)
 282 {
 283         struct symbol *res = NULL;
 284         struct symbol *sym;
 285         struct menu *menu;
 286
 287         /* Traverse the list of choice members in the priority order. */
 288         list_for_each_entry(sym, &choice->choice_members, choice_link) {
 289                 sym_calc_visibility(sym);
 290                 if (sym->visible == no)
 291                         continue;
 292
 293                 /* The first visible symble with the user value 'y'. */
 294                 if (sym_has_value(sym) && sym->def[S_DEF_USER].tri == yes) {
 295                         res = sym;
 296                         break;
 297                 }
 298         }
 299
 300         /*
 301          * If 'y' is not found in the user input, use the default, unless it is
 302          * explicitly set to 'n'.
 303          */
 304         if (!res) {
 305                 res = sym_choice_default(choice);
 306                 if (res && sym_has_value(res) && res->def[S_DEF_USER].tri == no)
 307                         res = NULL;
 308         }
 309
 310         /* Still not found. Pick up the first visible, user-unspecified symbol. */
 311         if (!res) {
 312                 menu_for_each_sub_entry(menu, choice) {
 313                         sym = menu->sym;
 314
 315                         if (!sym || sym->visible == no || sym_has_value(sym))
 316                                 continue;
 317
 318                         res = sym;
 319                         break;
 320                 }
 321         }
 322
 323         /*
 324          * Still not found. Traverse the linked list in the _reverse_ order to
 325          * pick up the least prioritized 'n'.
 326          */
 327         if (!res) {
 328                 list_for_each_entry_reverse(sym, &choice->choice_members,
 329                                             choice_link) {
 330                         if (sym->visible == no)
 331                                 continue;
 332
 333                         res = sym;
 334                         break;
 335                 }
 336         }
 337
 338         menu_for_each_sub_entry(menu, choice) {
 339                 tristate val;
 340
 341                 sym = menu->sym;
 342
 343                 if (!sym || sym->visible == no)
 344                         continue;
 345
 346                 val = sym == res ? yes : no;
 347
 348                 if (sym->curr.tri != val)
 349                         sym_set_changed(sym);
 350
 351                 sym->curr.tri = val;
 352                 sym->flags |= SYMBOL_VALID | SYMBOL_WRITE;
 353         }
 354
 355         return res;
 356 }
 357
 358 static void sym_warn_unmet_dep(const struct symbol *sym)
 359 {
 360         struct gstr gs = str_new();
 361
 362         str_printf(&gs,
 363                    "\nWARNING: unmet direct dependencies detected for %s\n",
 364                    sym->name);
 365         str_printf(&gs,
 366                    "  Depends on [%c]: ",
 367                    sym->dir_dep.tri == mod ? 'm' : 'n');
 368         expr_gstr_print(sym->dir_dep.expr, &gs);
 369         str_printf(&gs, "\n");
 370
 371         expr_gstr_print_revdep(sym->rev_dep.expr, &gs, yes,
 372                                "  Selected by [y]:\n");
 373         expr_gstr_print_revdep(sym->rev_dep.expr, &gs, mod,
 374                                "  Selected by [m]:\n");
 375
 376         fputs(str_get(&gs), stderr);
 377         sym_warnings++;
 378 }
 379
 380 bool sym_dep_errors(void)
 381 {
 382         if (sym_warnings)
 383                 return getenv("KCONFIG_WERROR");
 384         return false;
 385 }
 386
 387 void sym_calc_value(struct symbol *sym)
 388 {
 389         struct symbol_value newval, oldval;
 390         struct property *prop;
 391         struct menu *choice_menu;
 392
 393         if (!sym)
 394                 return;
 395
 396         if (sym->flags & SYMBOL_VALID)
 397                 return;
 398
 399         sym->flags |= SYMBOL_VALID;
 400
 401         oldval = sym->curr;
 402
 403         newval.tri = no;
 404
 405         switch (sym->type) {
 406         case S_INT:
 407                 newval.val = "0";
 408                 break;
 409         case S_HEX:
 410                 newval.val = "0x0";
 411                 break;
 412         case S_STRING:
 413                 newval.val = "";
 414                 break;
 415         case S_BOOLEAN:
 416         case S_TRISTATE:
 417                 newval.val = "n";
 418                 break;
 419         default:
 420                 sym->curr.val = sym->name;
 421                 sym->curr.tri = no;
 422                 return;
 423         }
 424         sym->flags &= ~SYMBOL_WRITE;
 425
 426         sym_calc_visibility(sym);
 427
 428         if (sym->visible != no)
 429                 sym->flags |= SYMBOL_WRITE;
 430
 431         /* set default if recursively called */
 432         sym->curr = newval;
 433
 434         switch (sym_get_type(sym)) {
 435         case S_BOOLEAN:
 436         case S_TRISTATE:
 437                 choice_menu = sym_get_choice_menu(sym);
 438
 439                 if (choice_menu) {
 440                         sym_calc_choice(choice_menu);
 441                         newval.tri = sym->curr.tri;
 442                 } else {
 443                         if (sym->visible != no) {
 444                                 /* if the symbol is visible use the user value
 445                                  * if available, otherwise try the default value
 446                                  */
 447                                 if (sym_has_value(sym)) {
 448                                         newval.tri = EXPR_AND(sym->def[S_DEF_USER].tri,
 449                                                               sym->visible);
 450                                         goto calc_newval;
 451                                 }
 452                         }
 453                         if (sym->rev_dep.tri != no)
 454                                 sym->flags |= SYMBOL_WRITE;
 455                         if (!sym_is_choice(sym)) {
 456                                 prop = sym_get_default_prop(sym);
 457                                 if (prop) {
 458                                         newval.tri = EXPR_AND(expr_calc_value(prop->expr),
 459                                                               prop->visible.tri);
 460                                         if (newval.tri != no)
 461                                                 sym->flags |= SYMBOL_WRITE;
 462                                 }
 463                                 if (sym->implied.tri != no) {
 464                                         sym->flags |= SYMBOL_WRITE;
 465                                         newval.tri = EXPR_OR(newval.tri, sym->implied.tri);
 466                                         newval.tri = EXPR_AND(newval.tri,
 467                                                               sym->dir_dep.tri);
 468                                 }
 469                         }
 470                 calc_newval:
 471                         if (sym->dir_dep.tri < sym->rev_dep.tri)
 472                                 sym_warn_unmet_dep(sym);
 473                         newval.tri = EXPR_OR(newval.tri, sym->rev_dep.tri);
 474                 }
 475                 if (newval.tri == mod && sym_get_type(sym) == S_BOOLEAN)
 476                         newval.tri = yes;
 477                 break;
 478         case S_STRING:
 479         case S_HEX:
 480         case S_INT:
 481                 if (sym->visible != no && sym_has_value(sym)) {
 482                         newval.val = sym->def[S_DEF_USER].val;
 483                         break;
 484                 }
 485                 prop = sym_get_default_prop(sym);
 486                 if (prop) {
 487                         struct symbol *ds = prop_get_symbol(prop);
 488                         if (ds) {
 489                                 sym->flags |= SYMBOL_WRITE;
 490                                 sym_calc_value(ds);
 491                                 newval.val = ds->curr.val;
 492                         }
 493                 }
 494                 break;
 495         default:
 496                 ;
 497         }
 498
 499         sym->curr = newval;
 500         sym_validate_range(sym);
 501
 502         if (memcmp(&oldval, &sym->curr, sizeof(oldval))) {
 503                 sym_set_changed(sym);
 504                 if (modules_sym == sym) {
 505                         sym_set_all_changed();
 506                         modules_val = modules_sym->curr.tri;
 507                 }
 508         }
 509
 510         if (sym_is_choice(sym))
 511                 sym->flags &= ~SYMBOL_WRITE;
 512 }
 513
 514 void sym_clear_all_valid(void)
 515 {
 516         struct symbol *sym;
 517
 518         for_all_symbols(sym)
 519                 sym->flags &= ~SYMBOL_VALID;
 520         conf_set_changed(true);
 521         sym_calc_value(modules_sym);
 522 }
 523
 524 bool sym_tristate_within_range(const struct symbol *sym, tristate val)
 525 {
 526         int type = sym_get_type(sym);
 527
 528         if (sym->visible == no)
 529                 return false;
 530
 531         if (type != S_BOOLEAN && type != S_TRISTATE)
 532                 return false;
 533
 534         if (type == S_BOOLEAN && val == mod)
 535                 return false;
 536         if (sym->visible <= sym->rev_dep.tri)
 537                 return false;
 538         return val >= sym->rev_dep.tri && val <= sym->visible;
 539 }
 540
 541 bool sym_set_tristate_value(struct symbol *sym, tristate val)
 542 {
 543         tristate oldval = sym_get_tristate_value(sym);
 544
 545         if (!sym_tristate_within_range(sym, val))
 546                 return false;
 547
 548         if (!(sym->flags & SYMBOL_DEF_USER) || sym->def[S_DEF_USER].tri != val) {
 549                 sym->def[S_DEF_USER].tri = val;
 550                 sym->flags |= SYMBOL_DEF_USER;
 551                 sym_set_changed(sym);
 552         }
 553
 554         if (oldval != val)
 555                 sym_clear_all_valid();
 556
 557         return true;
 558 }
 559
 560 /**
 561  * choice_set_value - set the user input to a choice
 562  *
 563  * @choice: menu entry for the choice
 564  * @sym: selected symbol
 565  */
 566 void choice_set_value(struct menu *choice, struct symbol *sym)
 567 {
 568         struct menu *menu;
 569         bool changed = false;
 570
 571         menu_for_each_sub_entry(menu, choice) {
 572                 tristate val;
 573
 574                 if (!menu->sym)
 575                         continue;
 576
 577                 if (menu->sym->visible == no)
 578                         continue;
 579
 580                 val = menu->sym == sym ? yes : no;
 581
 582                 if (menu->sym->curr.tri != val)
 583                         changed = true;
 584
 585                 menu->sym->def[S_DEF_USER].tri = val;
 586                 menu->sym->flags |= SYMBOL_DEF_USER;
 587
 588                 /*
 589                  * Now, the user has explicitly enabled or disabled this symbol,
 590                  * it should be given the highest priority. We are possibly
 591                  * setting multiple symbols to 'n', where the first symbol is
 592                  * given the least prioritized 'n'. This works well when the
 593                  * choice block ends up with selecting 'n' symbol.
 594                  * (see sym_calc_choice())
 595                  */
 596                 list_move(&menu->sym->choice_link, &choice->choice_members);
 597         }
 598
 599         if (changed)
 600                 sym_clear_all_valid();
 601 }
 602
 603 tristate sym_toggle_tristate_value(struct symbol *sym)
 604 {
 605         struct menu *choice;
 606         tristate oldval, newval;
 607
 608         choice = sym_get_choice_menu(sym);
 609         if (choice) {
 610                 choice_set_value(choice, sym);
 611                 return yes;
 612         }
 613
 614         oldval = newval = sym_get_tristate_value(sym);
 615         do {
 616                 switch (newval) {
 617                 case no:
 618                         newval = mod;
 619                         break;
 620                 case mod:
 621                         newval = yes;
 622                         break;
 623                 case yes:
 624                         newval = no;
 625                         break;
 626                 }
 627                 if (sym_set_tristate_value(sym, newval))
 628                         break;
 629         } while (oldval != newval);
 630         return newval;
 631 }
 632
 633 bool sym_string_valid(struct symbol *sym, const char *str)
 634 {
 635         signed char ch;
 636
 637         switch (sym->type) {
 638         case S_STRING:
 639                 return true;
 640         case S_INT:
 641                 ch = *str++;
 642                 if (ch == '-')
 643                         ch = *str++;
 644                 if (!isdigit(ch))
 645                         return false;
 646                 if (ch == '0' && *str != 0)
 647                         return false;
 648                 while ((ch = *str++)) {
 649                         if (!isdigit(ch))
 650                                 return false;
 651                 }
 652                 return true;
 653         case S_HEX:
 654                 if (str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
 655                         str += 2;
 656                 ch = *str++;
 657                 do {
 658                         if (!isxdigit(ch))
 659                                 return false;
 660                 } while ((ch = *str++));
 661                 return true;
 662         case S_BOOLEAN:
 663         case S_TRISTATE:
 664                 switch (str[0]) {
 665                 case 'y': case 'Y':
 666                 case 'm': case 'M':
 667                 case 'n': case 'N':
 668                         return true;
 669                 }
 670                 return false;
 671         default:
 672                 return false;
 673         }
 674 }
 675
 676 bool sym_string_within_range(struct symbol *sym, const char *str)
 677 {
 678         struct property *prop;
 679         long long val;
 680
 681         switch (sym->type) {
 682         case S_STRING:
 683                 return sym_string_valid(sym, str);
 684         case S_INT:
 685                 if (!sym_string_valid(sym, str))
 686                         return false;
 687                 prop = sym_get_range_prop(sym);
 688                 if (!prop)
 689                         return true;
 690                 val = strtoll(str, NULL, 10);
 691                 return val >= sym_get_range_val(prop->expr->left.sym, 10) &&
 692                        val <= sym_get_range_val(prop->expr->right.sym, 10);
 693         case S_HEX:
 694                 if (!sym_string_valid(sym, str))
 695                         return false;
 696                 prop = sym_get_range_prop(sym);
 697                 if (!prop)
 698                         return true;
 699                 val = strtoll(str, NULL, 16);
 700                 return val >= sym_get_range_val(prop->expr->left.sym, 16) &&
 701                        val <= sym_get_range_val(prop->expr->right.sym, 16);
 702         case S_BOOLEAN:
 703         case S_TRISTATE:
 704                 switch (str[0]) {
 705                 case 'y': case 'Y':
 706                         return sym_tristate_within_range(sym, yes);
 707                 case 'm': case 'M':
 708                         return sym_tristate_within_range(sym, mod);
 709                 case 'n': case 'N':
 710                         return sym_tristate_within_range(sym, no);
 711                 }
 712                 return false;
 713         default:
 714                 return false;
 715         }
 716 }
 717
 718 bool sym_set_string_value(struct symbol *sym, const char *newval)
 719 {
 720         const char *oldval;
 721         char *val;
 722         int size;
 723
 724         switch (sym->type) {
 725         case S_BOOLEAN:
 726         case S_TRISTATE:
 727                 switch (newval[0]) {
 728                 case 'y': case 'Y':
 729                         return sym_set_tristate_value(sym, yes);
 730                 case 'm': case 'M':
 731                         return sym_set_tristate_value(sym, mod);
 732                 case 'n': case 'N':
 733                         return sym_set_tristate_value(sym, no);
 734                 }
 735                 return false;
 736         default:
 737                 ;
 738         }
 739
 740         if (!sym_string_within_range(sym, newval))
 741                 return false;
 742
 743         if (!(sym->flags & SYMBOL_DEF_USER)) {
 744                 sym->flags |= SYMBOL_DEF_USER;
 745                 sym_set_changed(sym);
 746         }
 747
 748         oldval = sym->def[S_DEF_USER].val;
 749         size = strlen(newval) + 1;
 750         if (sym->type == S_HEX && (newval[0] != '0' || (newval[1] != 'x' && newval[1] != 'X'))) {
 751                 size += 2;
 752                 sym->def[S_DEF_USER].val = val = xmalloc(size);
 753                 *val++ = '0';
 754                 *val++ = 'x';
 755         } else if (!oldval || strcmp(oldval, newval))
 756                 sym->def[S_DEF_USER].val = val = xmalloc(size);
 757         else
 758                 return true;
 759
 760         strcpy(val, newval);
 761         free((void *)oldval);
 762         sym_clear_all_valid();
 763
 764         return true;
 765 }
 766
 767 /*
 768  * Find the default value associated to a symbol.
 769  * For tristate symbol handle the modules=n case
 770  * in which case "m" becomes "y".
 771  * If the symbol does not have any default then fallback
 772  * to the fixed default values.
 773  */
 774 const char *sym_get_string_default(struct symbol *sym)
 775 {
 776         struct property *prop;
 777         struct symbol *ds;
 778         const char *str = "";
 779         tristate val;
 780
 781         sym_calc_visibility(sym);
 782         sym_calc_value(modules_sym);
 783         val = symbol_no.curr.tri;
 784
 785         /* If symbol has a default value look it up */
 786         prop = sym_get_default_prop(sym);
 787         if (prop != NULL) {
 788                 switch (sym->type) {
 789                 case S_BOOLEAN:
 790                 case S_TRISTATE:
 791                         /* The visibility may limit the value from yes => mod */
 792                         val = EXPR_AND(expr_calc_value(prop->expr), prop->visible.tri);
 793                         break;
 794                 default:
 795                         /*
 796                          * The following fails to handle the situation
 797                          * where a default value is further limited by
 798                          * the valid range.
 799                          */
 800                         ds = prop_get_symbol(prop);
 801                         if (ds != NULL) {
 802                                 sym_calc_value(ds);
 803                                 str = (const char *)ds->curr.val;
 804                         }
 805                 }
 806         }
 807
 808         /* Handle select statements */
 809         val = EXPR_OR(val, sym->rev_dep.tri);
 810
 811         /* transpose mod to yes if modules are not enabled */
 812         if (val == mod)
 813                 if (!sym_is_choice_value(sym) && modules_sym->curr.tri == no)
 814                         val = yes;
 815
 816         /* transpose mod to yes if type is bool */
 817         if (sym->type == S_BOOLEAN && val == mod)
 818                 val = yes;
 819
 820         /* adjust the default value if this symbol is implied by another */
 821         if (val < sym->implied.tri)
 822                 val = sym->implied.tri;
 823
 824         switch (sym->type) {
 825         case S_BOOLEAN:
 826         case S_TRISTATE:
 827                 switch (val) {
 828                 case no: return "n";
 829                 case mod: return "m";
 830                 case yes: return "y";
 831                 }
 832         case S_INT:
 833                 if (!str[0])
 834                         str = "0";
 835                 break;
 836         case S_HEX:
 837                 if (!str[0])
 838                         str = "0x0";
 839                 break;
 840         default:
 841                 break;
 842         }
 843         return str;
 844 }
 845
 846 const char *sym_get_string_value(struct symbol *sym)
 847 {
 848         tristate val;
 849
 850         switch (sym->type) {
 851         case S_BOOLEAN:
 852         case S_TRISTATE:
 853                 val = sym_get_tristate_value(sym);
 854                 switch (val) {
 855                 case no:
 856                         return "n";
 857                 case mod:
 858                         return "m";
 859                 case yes:
 860                         return "y";
 861                 }
 862                 break;
 863         default:
 864                 ;
 865         }
 866         return (const char *)sym->curr.val;
 867 }
 868
 869 bool sym_is_changeable(const struct symbol *sym)
 870 {
 871         return !sym_is_choice(sym) && sym->visible > sym->rev_dep.tri;
 872 }
 873
 874 bool sym_is_choice_value(const struct symbol *sym)
 875 {
 876         return !list_empty(&sym->choice_link);
 877 }
 878
 879 HASHTABLE_DEFINE(sym_hashtable, SYMBOL_HASHSIZE);
 880
 881 struct symbol *sym_lookup(const char *name, int flags)
 882 {
 883         struct symbol *symbol;
 884         char *new_name;
 885         int hash;
 886
 887         if (name) {
 888                 if (name[0] && !name[1]) {
 889                         switch (name[0]) {
 890                         case 'y': return &symbol_yes;
 891                         case 'm': return &symbol_mod;
 892                         case 'n': return &symbol_no;
 893                         }
 894                 }
 895                 hash = strhash(name);
 896
 897                 hash_for_each_possible(sym_hashtable, symbol, node, hash) {
 898                         if (symbol->name &&
 899                             !strcmp(symbol->name, name) &&
 900                             (flags ? symbol->flags & flags
 901                                    : !(symbol->flags & SYMBOL_CONST)))
 902                                 return symbol;
 903                 }
 904                 new_name = xstrdup(name);
 905         } else {
 906                 new_name = NULL;
 907                 hash = 0;
 908         }
 909
 910         symbol = xmalloc(sizeof(*symbol));
 911         memset(symbol, 0, sizeof(*symbol));
 912         symbol->name = new_name;
 913         symbol->type = S_UNKNOWN;
 914         symbol->flags = flags;
 915         INIT_LIST_HEAD(&symbol->menus);
 916         INIT_LIST_HEAD(&symbol->choice_link);
 917
 918         hash_add(sym_hashtable, &symbol->node, hash);
 919
 920         return symbol;
 921 }
 922
 923 struct symbol *sym_find(const char *name)
 924 {
 925         struct symbol *symbol = NULL;
 926         int hash = 0;
 927
 928         if (!name)
 929                 return NULL;
 930
 931         if (name[0] && !name[1]) {
 932                 switch (name[0]) {
 933                 case 'y': return &symbol_yes;
 934                 case 'm': return &symbol_mod;
 935                 case 'n': return &symbol_no;
 936                 }
 937         }
 938         hash = strhash(name);
 939
 940         hash_for_each_possible(sym_hashtable, symbol, node, hash) {
 941                 if (symbol->name &&
 942                     !strcmp(symbol->name, name) &&
 943                     !(symbol->flags & SYMBOL_CONST))
 944                                 break;
 945         }
 946
 947         return symbol;
 948 }
 949
 950 struct sym_match {
 951         struct symbol   *sym;
 952         off_t           so, eo;
 953 };
 954
 955 /* Compare matched symbols as thus:
 956  * - first, symbols that match exactly
 957  * - then, alphabetical sort
 958  */
 959 static int sym_rel_comp(const void *sym1, const void *sym2)
 960 {
 961         const struct sym_match *s1 = sym1;
 962         const struct sym_match *s2 = sym2;
 963         int exact1, exact2;
 964
 965         /* Exact match:
 966          * - if matched length on symbol s1 is the length of that symbol,
 967          *   then this symbol should come first;
 968          * - if matched length on symbol s2 is the length of that symbol,
 969          *   then this symbol should come first.
 970          * Note: since the search can be a regexp, both symbols may match
 971          * exactly; if this is the case, we can't decide which comes first,
 972          * and we fallback to sorting alphabetically.
 973          */
 974         exact1 = (s1->eo - s1->so) == strlen(s1->sym->name);
 975         exact2 = (s2->eo - s2->so) == strlen(s2->sym->name);
 976         if (exact1 && !exact2)
 977                 return -1;
 978         if (!exact1 && exact2)
 979                 return 1;
 980
 981         /* As a fallback, sort symbols alphabetically */
 982         return strcmp(s1->sym->name, s2->sym->name);
 983 }
 984
 985 struct symbol **sym_re_search(const char *pattern)
 986 {
 987         struct symbol *sym, **sym_arr = NULL;
 988         struct sym_match *sym_match_arr = NULL;
 989         int i, cnt, size;
 990         regex_t re;
 991         regmatch_t match[1];
 992
 993         cnt = size = 0;
 994         /* Skip if empty */
 995         if (strlen(pattern) == 0)
 996                 return NULL;
 997         if (regcomp(&re, pattern, REG_EXTENDED|REG_ICASE))
 998                 return NULL;
 999
1000         for_all_symbols(sym) {
1001                 if (sym->flags & SYMBOL_CONST || !sym->name)
1002                         continue;
1003                 if (regexec(&re, sym->name, 1, match, 0))
1004                         continue;
1005                 if (cnt >= size) {
1006                         void *tmp;
1007                         size += 16;
1008                         tmp = realloc(sym_match_arr, size * sizeof(struct sym_match));
1009                         if (!tmp)
1010                                 goto sym_re_search_free;
1011                         sym_match_arr = tmp;
1012                 }
1013                 sym_calc_value(sym);
1014                 /* As regexec returned 0, we know we have a match, so
1015                  * we can use match[0].rm_[se]o without further checks
1016                  */
1017                 sym_match_arr[cnt].so = match[0].rm_so;
1018                 sym_match_arr[cnt].eo = match[0].rm_eo;
1019                 sym_match_arr[cnt++].sym = sym;
1020         }
1021         if (sym_match_arr) {
1022                 qsort(sym_match_arr, cnt, sizeof(struct sym_match), sym_rel_comp);
1023                 sym_arr = malloc((cnt+1) * sizeof(struct symbol *));
1024                 if (!sym_arr)
1025                         goto sym_re_search_free;
1026                 for (i = 0; i < cnt; i++)
1027                         sym_arr[i] = sym_match_arr[i].sym;
1028                 sym_arr[cnt] = NULL;
1029         }
1030 sym_re_search_free:
1031         /* sym_match_arr can be NULL if no match, but free(NULL) is OK */
1032         free(sym_match_arr);
1033         regfree(&re);
1034
1035         return sym_arr;
1036 }
1037
1038 /*
1039  * When we check for recursive dependencies we use a stack to save
1040  * current state so we can print out relevant info to user.
1041  * The entries are located on the call stack so no need to free memory.
1042  * Note insert() remove() must always match to properly clear the stack.
1043  */
1044 static struct dep_stack {
1045         struct dep_stack *prev, *next;
1046         struct symbol *sym;
1047         struct property *prop;
1048         struct expr **expr;
1049 } *check_top;
1050
1051 static void dep_stack_insert(struct dep_stack *stack, struct symbol *sym)
1052 {
1053         memset(stack, 0, sizeof(*stack));
1054         if (check_top)
1055                 check_top->next = stack;
1056         stack->prev = check_top;
1057         stack->sym = sym;
1058         check_top = stack;
1059 }
1060
1061 static void dep_stack_remove(void)
1062 {
1063         check_top = check_top->prev;
1064         if (check_top)
1065                 check_top->next = NULL;
1066 }
1067
1068 /*
1069  * Called when we have detected a recursive dependency.
1070  * check_top point to the top of the stact so we use
1071  * the ->prev pointer to locate the bottom of the stack.
1072  */
1073 static void sym_check_print_recursive(struct symbol *last_sym)
1074 {
1075         struct dep_stack *stack;
1076         struct symbol *sym, *next_sym;
1077         struct menu *choice;
1078         struct dep_stack cv_stack;
1079         enum prop_type type;
1080
1081         choice = sym_get_choice_menu(last_sym);
1082         if (choice) {
1083                 dep_stack_insert(&cv_stack, last_sym);
1084                 last_sym = choice->sym;
1085         }
1086
1087         for (stack = check_top; stack != NULL; stack = stack->prev)
1088                 if (stack->sym == last_sym)
1089                         break;
1090         if (!stack) {
1091                 fprintf(stderr, "unexpected recursive dependency error\n");
1092                 return;
1093         }
1094
1095         for (; stack; stack = stack->next) {
1096                 sym = stack->sym;
1097                 next_sym = stack->next ? stack->next->sym : last_sym;
1098                 type = stack->prop ? stack->prop->type : P_UNKNOWN;
1099
1100                 if (stack->sym == last_sym)
1101                         fprintf(stderr, "error: recursive dependency detected!\n");
1102
1103                 if (sym_is_choice(next_sym)) {
1104                         choice = list_first_entry(&next_sym->menus, struct menu, link);
1105
1106                         fprintf(stderr, "\tsymbol %s is part of choice block at %s:%d\n",
1107                                 sym->name ? sym->name : "<choice>",
1108                                 choice->filename, choice->lineno);
1109                 } else if (stack->expr == &sym->dir_dep.expr) {
1110                         fprintf(stderr, "\tsymbol %s depends on %s\n",
1111                                 sym->name ? sym->name : "<choice>",
1112                                 next_sym->name);
1113                 } else if (stack->expr == &sym->rev_dep.expr) {
1114                         fprintf(stderr, "\tsymbol %s is selected by %s\n",
1115                                 sym->name, next_sym->name);
1116                 } else if (stack->expr == &sym->implied.expr) {
1117                         fprintf(stderr, "\tsymbol %s is implied by %s\n",
1118                                 sym->name, next_sym->name);
1119                 } else if (stack->expr) {
1120                         fprintf(stderr, "\tsymbol %s %s value contains %s\n",
1121                                 sym->name ? sym->name : "<choice>",
1122                                 prop_get_type_name(type),
1123                                 next_sym->name);
1124                 } else {
1125                         fprintf(stderr, "\tsymbol %s %s is visible depending on %s\n",
1126                                 sym->name ? sym->name : "<choice>",
1127                                 prop_get_type_name(type),
1128                                 next_sym->name);
1129                 }
1130         }
1131
1132         fprintf(stderr,
1133                 "For a resolution refer to Documentation/kbuild/kconfig-language.rst\n"
1134                 "subsection \"Kconfig recursive dependency limitations\"\n"
1135                 "\n");
1136
1137         if (check_top == &cv_stack)
1138                 dep_stack_remove();
1139 }
1140
1141 static struct symbol *sym_check_expr_deps(const struct expr *e)
1142 {
1143         struct symbol *sym;
1144
1145         if (!e)
1146                 return NULL;
1147         switch (e->type) {
1148         case E_OR:
1149         case E_AND:
1150                 sym = sym_check_expr_deps(e->left.expr);
1151                 if (sym)
1152                         return sym;
1153                 return sym_check_expr_deps(e->right.expr);
1154         case E_NOT:
1155                 return sym_check_expr_deps(e->left.expr);
1156         case E_EQUAL:
1157         case E_GEQ:
1158         case E_GTH:
1159         case E_LEQ:
1160         case E_LTH:
1161         case E_UNEQUAL:
1162                 sym = sym_check_deps(e->left.sym);
1163                 if (sym)
1164                         return sym;
1165                 return sym_check_deps(e->right.sym);
1166         case E_SYMBOL:
1167                 return sym_check_deps(e->left.sym);
1168         default:
1169                 break;
1170         }
1171         fprintf(stderr, "Oops! How to check %d?\n", e->type);
1172         return NULL;
1173 }
1174
1175 /* return NULL when dependencies are OK */
1176 static struct symbol *sym_check_sym_deps(struct symbol *sym)
1177 {
1178         struct symbol *sym2;
1179         struct property *prop;
1180         struct dep_stack stack;
1181
1182         dep_stack_insert(&stack, sym);
1183
1184         stack.expr = &sym->dir_dep.expr;
1185         sym2 = sym_check_expr_deps(sym->dir_dep.expr);
1186         if (sym2)
1187                 goto out;
1188
1189         stack.expr = &sym->rev_dep.expr;
1190         sym2 = sym_check_expr_deps(sym->rev_dep.expr);
1191         if (sym2)
1192                 goto out;
1193
1194         stack.expr = &sym->implied.expr;
1195         sym2 = sym_check_expr_deps(sym->implied.expr);
1196         if (sym2)
1197                 goto out;
1198
1199         stack.expr = NULL;
1200
1201         for (prop = sym->prop; prop; prop = prop->next) {
1202                 if (prop->type == P_SELECT || prop->type == P_IMPLY)
1203                         continue;
1204                 stack.prop = prop;
1205                 sym2 = sym_check_expr_deps(prop->visible.expr);
1206                 if (sym2)
1207                         break;
1208                 if (prop->type != P_DEFAULT || sym_is_choice(sym))
1209                         continue;
1210                 stack.expr = &prop->expr;
1211                 sym2 = sym_check_expr_deps(prop->expr);
1212                 if (sym2)
1213                         break;
1214                 stack.expr = NULL;
1215         }
1216
1217 out:
1218         dep_stack_remove();
1219
1220         return sym2;
1221 }
1222
1223 static struct symbol *sym_check_choice_deps(struct symbol *choice)
1224 {
1225         struct menu *choice_menu, *menu;
1226         struct symbol *sym2;
1227         struct dep_stack stack;
1228
1229         dep_stack_insert(&stack, choice);
1230
1231         choice_menu = list_first_entry(&choice->menus, struct menu, link);
1232
1233         menu_for_each_sub_entry(menu, choice_menu) {
1234                 if (menu->sym)
1235                         menu->sym->flags |= SYMBOL_CHECK | SYMBOL_CHECKED;
1236         }
1237
1238         choice->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
1239         sym2 = sym_check_sym_deps(choice);
1240         choice->flags &= ~SYMBOL_CHECK;
1241         if (sym2)
1242                 goto out;
1243
1244         menu_for_each_sub_entry(menu, choice_menu) {
1245                 if (!menu->sym)
1246                         continue;
1247                 sym2 = sym_check_sym_deps(menu->sym);
1248                 if (sym2)
1249                         break;
1250         }
1251 out:
1252         menu_for_each_sub_entry(menu, choice_menu)
1253                 if (menu->sym)
1254                         menu->sym->flags &= ~SYMBOL_CHECK;
1255
1256         if (sym2) {
1257                 struct menu *choice_menu2;
1258
1259                 choice_menu2 = sym_get_choice_menu(sym2);
1260                 if (choice_menu2 == choice_menu)
1261                         sym2 = choice;
1262         }
1263
1264         dep_stack_remove();
1265
1266         return sym2;
1267 }
1268
1269 struct symbol *sym_check_deps(struct symbol *sym)
1270 {
1271         struct menu *choice;
1272         struct symbol *sym2;
1273
1274         if (sym->flags & SYMBOL_CHECK) {
1275                 sym_check_print_recursive(sym);
1276                 return sym;
1277         }
1278         if (sym->flags & SYMBOL_CHECKED)
1279                 return NULL;
1280
1281         choice = sym_get_choice_menu(sym);
1282         if (choice) {
1283                 struct dep_stack stack;
1284
1285                 /* for choice groups start the check with main choice symbol */
1286                 dep_stack_insert(&stack, sym);
1287                 sym2 = sym_check_deps(choice->sym);
1288                 dep_stack_remove();
1289         } else if (sym_is_choice(sym)) {
1290                 sym2 = sym_check_choice_deps(sym);
1291         } else {
1292                 sym->flags |= (SYMBOL_CHECK | SYMBOL_CHECKED);
1293                 sym2 = sym_check_sym_deps(sym);
1294                 sym->flags &= ~SYMBOL_CHECK;
1295         }
1296
1297         return sym2;
1298 }
1299
1300 struct symbol *prop_get_symbol(const struct property *prop)
1301 {
1302         if (prop->expr && prop->expr->type == E_SYMBOL)
1303                 return prop->expr->left.sym;
1304         return NULL;
1305 }
1306
1307 const char *prop_get_type_name(enum prop_type type)
1308 {
1309         switch (type) {
1310         case P_PROMPT:
1311                 return "prompt";
1312         case P_COMMENT:
1313                 return "comment";
1314         case P_MENU:
1315                 return "menu";
1316         case P_DEFAULT:
1317                 return "default";
1318         case P_SELECT:
1319                 return "select";
1320         case P_IMPLY:
1321                 return "imply";
1322         case P_RANGE:
1323                 return "range";
1324         case P_SYMBOL:
1325                 return "symbol";
1326         case P_UNKNOWN:
1327                 break;
1328         }
1329         return "unknown";
1330 }