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