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