Debian Codegraph @

src/complexity.c

raw
1
2 /*
3 * This file is part of Complexity.
4 * Complexity Copyright (c) 2011-2020 by Bruce Korb - all rights reserved
5 *
6 * Complexity is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * Complexity is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 * See the GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License along
17 * with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #define _GNU_SOURCE 1
21
22 #include "opts.h"
23 #include <limits.h>
24 #include <math.h>
25 #include <regex.h>
26 #include <stdlib.h>
27 #include <unistd.h>
28
29 #ifndef UNIFDEF_EXE
30 #define UNIFDEF_EXE "unifdef"
31 #endif
32
33 #define RANGE_LIMIT 2000
34
35 static score_t score_ttl = 0;
36 static int ttl_line_ct = 0;
37 static int unscore_ct = 0;
38 static int high_score = 0;
39 score_t subexp_penalty = 0;
40 score_t threshold = 0;
41 score_t scaling;
42
43 static char const head_fmt[] = "Complexity Scores\n"
44 "Score | ln-ct | nc-lns| file-name(line): proc-name\n";
45 static char const line_fmt[] = "%5d %6d %6d %s(%d): %s\n";
46 static char const lnct_fmt[] = "total nc-lns %8d\n";
47 static char const bad_line_fmt[] = "***** %6d %6d %s(%d): %s\n";
48 static char const nomem_fmt[] = "could not allocate %d bytes\n";
49
50 static int score_alloc_ct = 0;
51 static state_t ** scores = NULL;
52
53 static char const * unifcmd = UNIFDEF_EXE;
54 static char high_buf[1024];
55
56 void
57 initialize(int argc, char ** argv)
58 {
59 if (HAVE_OPT(INPUT) && (argc > 0)) {
60 static char const oops[] =
61 "source files were specified both on the command line "
62 "and with the --input option.\n";
63 fwrite(oops, sizeof(oops)-1, 1, stderr);
64 USAGE(EXIT_FAILURE);
65 }
66
67 if (! HAVE_OPT(SCORES)) {
68 if (! ENABLED_OPT(HISTOGRAM))
69 SET_OPT_SCORES;
70
71 else if (! HAVE_OPT(THRESHOLD))
72 /*
73 * No scores, doing a histogram and have not specified a threshold.
74 */
75 SET_OPT_THRESHOLD(0);
76 }
77
78 if (HAVE_OPT(NESTING_PENALTY)) {
79 penalty = atof(OPT_ARG(NESTING_PENALTY));
80 if (penalty < 1.0)
81 penalty = DEFAULT_PENALTY;
82 }
83
84 if (HAVE_OPT(DEMI_NESTING_PENALTY))
85 subexp_penalty = atof(OPT_ARG(DEMI_NESTING_PENALTY));
86
87 if (subexp_penalty < 1.0)
88 subexp_penalty = sqrt(penalty);
89
90 threshold = (score_t)OPT_VALUE_THRESHOLD - 0.5;
91
92 scores = malloc(1024 * sizeof(*scores));
93 score_alloc_ct = 1024;
94 scaling = (score_t)(HAVE_OPT(SCALE) ? OPT_VALUE_SCALE : DEFAULT_SCALE);
95 scaling = 1.0 / scaling;
96 }
97
98 static inline int
99 hash_score(score_t score)
100 {
101 int sc = score + 0.5;
102 if (sc < 10) return 0;
103 if (sc < 100) return sc / 10; // 1 -> 9
104 if (sc < 1000) return 9 + (sc / 100); // 10 -> 18
105 return 18 + (sc / 1000); // 19 -> ...
106 }
107
108 static inline bool
109 check_skip(int * scores, int ix, int lim, bool skip_now)
110 {
111 if (skip_now)
112 return skip_now; // have zero and already skipping
113 /*
114 * First zero count in a sequence.
115 */
116 if ((ix + 1) < lim)
117 return false; // no more lines, so do not ignore.
118 if (scores[ix + 1] != 0)
119 return false; // next not zero, so report zero
120 return true; // next is zero too, so start zero sequence
121 }
122
123 static void
124 print_histogram(void)
125 {
126 static char const hsthdr[] =
127 "Complexity Histogram\n"
128 "Score-Range Lin-Ct\n";
129 static char const stars[] =
130 "************************************************************";
131 static int const starct = sizeof(stars) - 1;
132 static char const fmtfmt[] = "%%5d-%%-5d %%7d %%%1$d.%1$ds\n";
133 static char const deffmt[] = "%5d-%-5d %7d\n";
134
135 int const score_ix_lim = hash_score(scores[score_ct-1]->score) + 1;
136
137 int * lines_scoring = calloc(score_ix_lim, sizeof(int));
138 int max_ct = 0;
139
140 for (int ix = 0; ix < score_ct; ix++) {
141 int score_ix = hash_score(scores[ix]->score);
142
143 lines_scoring[score_ix] += scores[ix]->st_nc_line_ct;
144 if (lines_scoring[score_ix] > max_ct)
145 max_ct = lines_scoring[score_ix];
146 }
147
148 if (! HAVE_OPT(NO_HEADER)) {
149 if (ENABLED_OPT(SCORES))
150 putc(NL, stdout);
151 fwrite(hsthdr, sizeof(hsthdr) - 1, 1, stdout);
152 }
153
154 int min_score = 0;
155 int score_inc = 10;
156 int hi_score = min_score + score_inc - 1;
157 bool skipping = true;
158 bool first_line = true;
159
160 for (int ix = 0;
161 ix < score_ix_lim;
162 ix++, min_score = hi_score + 1, hi_score += score_inc) {
163 int ct = lines_scoring[ix];
164 bool put_nl = false;
165
166 switch (min_score) {
167 case 90: score_inc = 100; put_nl = true; break;
168 case 900: score_inc = 1000; put_nl = true; break;
169 }
170
171 if (ct == 0) {
172 skipping = check_skip(lines_scoring, ix, score_ix_lim, skipping);
173 if (skipping)
174 continue;
175 }
176
177 /*
178 * We are not skipping any more. If we were, put out a marker.
179 */
180 if (skipping) {
181 if (! first_line)
182 fputs("**********\n", stdout);
183 skipping = first_line = false;
184 }
185
186 int width = ((starct * ct) + (max_ct/2)) / max_ct;
187 if (width > 0) {
188 char fmt[64];
189 width = snprintf(fmt, sizeof(fmt), fmtfmt, width);
190 printf(fmt, min_score, hi_score, ct, stars);
191 } else
192 printf(deffmt, min_score, hi_score, ct);
193
194 if (put_nl)
195 putc(NL, stdout);
196 }
197
198 free(lines_scoring);
199 }
200
201 static void
202 print_stats(void)
203 {
204 #define SUMMARY_TABLE \
205 _St_("Scored procedure ct: %7d\n", score_ct) \
206 _St_("Non-comment line ct: %7d\n", ttl_line_ct) \
207 _St_("Average line score: %7d\n", \
208 (int)(av_score + 0.5)) \
209 _St_("25%%-ile score: %7d (75%% in higher score procs)\n", \
210 pctile[0]) \
211 _St_("50%%-ile score: %7d (half in higher score procs)\n", \
212 pctile[1]) \
213 _St_("75%%-ile score: %7d (25%% in higher score procs)\n", \
214 pctile[2]) \
215 _St_("Highest score: %7d", high_score) \
216 _St_(" (%s)\n", high_buf)
217
218 #define _St_(_s, _a) _s
219 static char const summary_fmt[] = "\n" SUMMARY_TABLE;
220 #undef _St_
221
222 score_t av_score = score_ttl / ttl_line_ct;
223 int pctile[5] = { 0, 0, 0, 0, 0 };
224 int pct_ix = 0;
225 int counter = 0;
226 int ix;
227 int pct_ct = ttl_line_ct / 4;
228 int pct_thresh = pct_ct;
229
230 for (ix = 0; ix < score_ct; ix++) {
231 counter += scores[ix]->st_nc_line_ct;
232
233 if (counter >= pct_thresh) {
234 pctile[pct_ix++] = (int)(scores[ix]->score + 0.5);
235 pct_thresh += pct_ct;
236 }
237 }
238
239 #define _St_(_s, _a) , _a
240 printf(summary_fmt SUMMARY_TABLE);
241 #undef _St_
242
243 if (unscore_ct > 0)
244 printf("Unscored procedures: %7d\n", unscore_ct);
245 #undef SUMMARY_TABLE
246 }
247
248 static int
249 compare_score(void const * a, void const * b)
250 {
251 state_t * A = *(void **)a;
252 state_t * B = *(void **)b;
253 int res = (int)(A->score - B->score);
254 if (res != 0)
255 return res;
256 res = A->st_nc_line_ct - B->st_nc_line_ct;
257 if (res != 0)
258 return res;
259 return A->st_line_ct - B->st_line_ct;
260 }
261
262 void
263 do_summary(complexity_exit_code_t exit_code)
264 {
265 qsort(scores, score_ct, sizeof(state_t *), compare_score);
266 if (ENABLED_OPT(SCORES)) {
267 if (! HAVE_OPT(NO_HEADER))
268 fwrite(head_fmt, sizeof(head_fmt) - 1, 1, stdout);
269
270 for (int ix = 0; ix < score_ct; ix++) {
271 int val = scores[ix]->score + 0.5;
272 printf(line_fmt, val, scores[ix]->st_line_ct,
273 scores[ix]->st_nc_line_ct,
274 scores[ix]->st_end, scores[ix]->ln_st, scores[ix]->pname);
275 }
276 }
277 if (HAVE_OPT(HISTOGRAM)) {
278 print_histogram();
279 print_stats();
280
281 } else if (! HAVE_OPT(NO_HEADER))
282 printf(lnct_fmt, ttl_line_ct);
283 }
284
285 static FILE *
286 popen_unifdef(char const * fname)
287 {
288 static char const * cmd = NULL;
289 static size_t cmdlen = 0;
290
291 if (cmd == NULL) {
292 int ct = STACKCT_OPT(UNIFDEF);
293 char const * const * ov = STACKLST_OPT(UNIFDEF);
294 char * buf;
295 size_t len;
296
297 /*
298 * Select the correct unifdef command and add one to the length:
299 * for NUL termination. Then add up the lengths of the arguments
300 * and space separations we need.
301 */
302 if (HAVE_OPT(UNIF_EXE))
303 unifcmd = OPT_ARG(UNIF_EXE);
304 len = cmdlen = strlen(unifcmd) + 1;
305
306 for (int i = 0; i < ct; i++)
307 len += 1 + strlen(ov[i]);
308
309 cmd = buf = malloc(len);
310 if (buf == NULL)
311 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, len);
312
313 /*
314 * Now assemble the command
315 */
316 memcpy(buf, unifcmd, cmdlen);
317 buf += cmdlen - 1;
318
319 while (ct-- > 0) {
320 char const * p = *(ov++);
321 *(buf++) = ' ';
322 len = strlen(p);
323 memcpy(buf, p, len);
324 buf += len;
325 }
326 *buf = NUL;
327 cmdlen = (buf - cmd) + 2;
328 }
329
330 {
331 size_t bfsz = cmdlen + strlen(fname);
332 char * bf = malloc(bfsz);
333 FILE * res;
334 if (bf == NULL)
335 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, bfsz);
336 size_t sz = snprintf(bf, bfsz, "%s %s", cmd, fname);
337 CX_ASSERT(sz < bfsz);
338
339 res = popen(bf, "r");
340 free(bf);
341 return res;
342 }
343 }
344
345 static bool
346 load_file(fstate_t * fs)
347 {
348 unsigned long const pgsz = sysconf(_SC_PAGE_SIZE);
349 off_t fsiz = pgsz * 4;
350 off_t foff = 0;
351 bool is_guess = true;
352 char * full_text;
353 char * rdp;
354
355 {
356 struct stat sb;
357 if (fstat(fileno(fs->fs_fp), &sb) >= 0) {
358 if (S_ISREG(sb.st_mode)) {
359 fsiz = sb.st_size + 1;
360 is_guess = false;
361 }
362 }
363 }
364
365 rdp = full_text = malloc(fsiz);
366 if (full_text == NULL)
367 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, fsiz);
368
369 for (;;) {
370 size_t ct = fsiz - foff;
371 size_t rdct = fread(rdp, 1, ct, fs->fs_fp);
372
373 if ((rdct < ct) || (! is_guess)) {
374 rdp[rdct] = '\0';
375 break;
376 }
377
378 /*
379 * We've filled out buffer and we don't know final size.
380 *
381 * 4, 6, 9, 13, 19, 28, ... pages
382 */
383 fsiz += (fsiz / 2) & ~(pgsz - 1);
384 full_text = realloc(full_text, fsiz);
385 if (full_text == NULL)
386 die(COMPLEXITY_EXIT_NOMEM,
387 "reallocation of %d to %d bytes failed\n",
388 (fsiz * 2) / 3, fsiz);
389
390 foff += rdct;
391 rdp = full_text + foff;
392 }
393
394 fs->fs_text = fs->fs_scan = full_text;
395 fs->cur_line = 1;
396 fs->nc_line = 0;
397 fs->fs_bol = true;
398 fs->last_tkn = TKN_EOF;
399 if (HAVE_OPT(TRACE))
400 fprintf(trace_fp, "\nLoading file %s\n", fs->fs_fname);
401 return true;
402 }
403
404 static bool
405 add_score(state_t * pstate)
406 {
407 if (threshold > pstate->score)
408 return false;
409
410 int val = (int)(pstate->score);
411
412 if (val >= MAX_SCORE) {
413 fprintf(stderr, "unscored: %s in %s on line %d\n",
414 pstate->pname, pstate->st_fstate->fs_fname, pstate->proc_line);
415 unscore_ct++;
416 return false;
417 }
418
419 if (val > high_score) {
420 snprintf(high_buf, sizeof(high_buf), "%s() in %s",
421 pstate->pname, pstate->st_fstate->fs_fname);
422 high_score = val;
423 }
424
425 return true;
426 }
427
428 static void
429 re_die(int code, regex_t * re, char const * pat)
430 {
431 char msg[64];
432 (void)regerror(code, re, msg, sizeof(msg));
433 die(COMPLEXITY_EXIT_ASSERT, "re error %s (%u) compiling ''%s''\n",
434 msg, (unsigned)code, pat);
435 }
436
437 static regex_t *
438 re_compile(void)
439 {
440 static char const pat[] = "[\r\n]\\}";
441
442 regex_t * res = malloc(sizeof(*res));
443 if (res == NULL)
444 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, (int)sizeof(*res));
445
446 {
447 int reres = regcomp(res, pat, REG_EXTENDED);
448 if (reres != 0)
449 re_die(reres, res, pat);
450 }
451
452 return res;
453 }
454
455 static bool
456 find_proc_end(state_t * ps, regex_t * re)
457 {
458 regmatch_t match;
459 char * scan = BRK_END_OF_LINE_CHARS(ps->st_fstate->fs_scan);
460
461 /*
462 * special case a one-line function (where opening and closing
463 * braces are on the same line).
464 */
465 {
466 char * close_brace = strchr(ps->st_fstate->fs_scan, '}');
467 if (close_brace == NULL)
468 return false;
469
470 if (close_brace < scan) {
471 ps->st_end = close_brace + 1; // same line
472 return true;
473 }
474 }
475
476 /*
477 * run the regex looking for a CR or LF preceding a '}'
478 */
479 if (regexec(re, scan, 1, &match, 0) != 0)
480 return false;
481 ps->st_end = scan + match.rm_eo;
482 return true;
483 }
484
485 static bool
486 do_proc(fstate_t * fs)
487 {
488 bool res = true;
489 static regex_t * re = NULL;
490 state_t * pstate = malloc(sizeof(*pstate));
491 if (pstate == NULL)
492 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, (int)sizeof(*pstate));
493
494 if (re == NULL)
495 re = re_compile();
496
497 state_init(pstate, fs);
498
499 if (! find_proc_end(pstate, re))
500 goto all_done;
501
502 if (HAVE_OPT(IGNORE)) {
503 int ct = STACKCT_OPT(IGNORE);
504 char const ** il = STACKLST_OPT(IGNORE);
505
506 do {
507 if (strcmp(*(il++), pstate->pname) == 0)
508 goto skip_proc;
509 } while (--ct > 0);
510 }
511
512 pstate->proc_line = fs->cur_line;
513
514 score_proc(pstate);
515 if (! add_score(pstate))
516 goto skip_proc;
517
518 if (pstate->st_nc_line_ct == 0) {
519 pstate->score = 0;
520 } else {
521 score_ttl += (pstate->score * pstate->st_nc_line_ct);
522 ttl_line_ct += pstate->st_nc_line_ct;
523 }
524
525 if (++score_ct >= score_alloc_ct) {
526 score_alloc_ct += score_alloc_ct / 2;
527 size_t sz = score_alloc_ct * sizeof(*scores);
528 scores = realloc(scores, sz);
529 if (scores == NULL)
530 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, sz);
531 }
532
533 pstate->st_end = (char *)fs->fs_fname;
534 scores[score_ct-1] = pstate;
535 return res;
536
537 skip_proc:
538
539 while (fs->fs_scan < pstate->st_end) {
540 if (fs->fs_scan[0] == NL)
541 fs->cur_line++;
542 fs->fs_scan++;
543 }
544
545 all_done:
546
547 free(pstate);
548 return res;
549 }
550
551 complexity_exit_code_t
552 complex_eval(char const * fname)
553 {
554 complexity_exit_code_t res = COMPLEXITY_EXIT_SUCCESS;
555
556 fstate_t fstate = {
557 .fs_fp = HAVE_OPT(UNIFDEF) ? popen_unifdef(fname) : fopen(fname, "r"),
558 .fs_fname = fname
559 };
560
561 if (fstate.fs_fp == NULL)
562 return COMPLEXITY_EXIT_BAD_FILE;
563
564 if (! load_file(&fstate))
565 return COMPLEXITY_EXIT_BAD_FILE;
566
567 int proc_ct = strlen(fname) + 1;
568 fname = strdup(fname);
569 if (fname == NULL)
570 die(COMPLEXITY_EXIT_NOMEM, nomem_fmt, proc_ct);
571 proc_ct = 0;
572
573 while (find_proc_start(&fstate))
574 if (! do_proc(&fstate))
575 break;
576
577 fflush(stdout);
578 free((void *)fstate.fs_text);
579
580 HAVE_OPT(UNIFDEF) ? pclose(fstate.fs_fp) : fclose(fstate.fs_fp);
581
582 if (high_score > OPT_VALUE_HORRID_THRESHOLD)
583 res = COMPLEXITY_EXIT_HORRID_FUNCTION;
584
585 return res;
586 }
587 /*
588 * Local Variables:
589 * mode: C
590 * c-file-style: "stroustrup"
591 * indent-tabs-mode: nil
592 * End:
593 * end of complexity.c */