commiting:
[people/mcb30/busybox.git] / scripts / mkdep.c
1 /*
2  * Originally by Linus Torvalds.
3  * Smart CONFIG_* processing by Werner Almesberger, Michael Chastain.
4  *
5  * Usage: mkdep cflags -- file ...
6  *
7  * Read source files and output makefile dependency lines for them.
8  * I make simple dependency lines for #include <*.h> and #include "*.h".
9  * I also find instances of CONFIG_FOO and generate dependencies
10  *    like include/config/foo.h.
11  *
12  * 1 August 1999, Michael Elizabeth Chastain, <mec@shout.net>
13  * - Keith Owens reported a bug in smart config processing.  There used
14  *   to be an optimization for "#define CONFIG_FOO ... #ifdef CONFIG_FOO",
15  *   so that the file would not depend on CONFIG_FOO because the file defines
16  *   this symbol itself.  But this optimization is bogus!  Consider this code:
17  *   "#if 0 \n #define CONFIG_FOO \n #endif ... #ifdef CONFIG_FOO".  Here
18  *   the definition is inactivated, but I still used it.  It turns out this
19  *   actually happens a few times in the kernel source.  The simple way to
20  *   fix this problem is to remove this particular optimization.
21  *
22  * 2.3.99-pre1, Andrew Morton <andrewm@uow.edu.au>
23  * - Changed so that 'filename.o' depends upon 'filename.[cS]'.  This is so that
24  *   missing source files are noticed, rather than silently ignored.
25  *
26  * 2.4.2-pre3, Keith Owens <kaos@ocs.com.au>
27  * - Accept cflags followed by '--' followed by filenames.  mkdep extracts -I
28  *   options from cflags and looks in the specified directories as well as the
29  *   defaults.   Only -I is supported, no attempt is made to handle -idirafter,
30  *   -isystem, -I- etc.
31  */
32
33 #include <ctype.h>
34 #include <fcntl.h>
35 #include <limits.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <unistd.h>
40
41 #include <sys/fcntl.h>
42 #include <sys/mman.h>
43 #include <sys/stat.h>
44 #include <sys/types.h>
45
46
47
48 char depname[512];
49 int hasdep;
50
51 struct path_struct {
52         int len;
53         char *buffer;
54 };
55 struct path_struct *path_array;
56 int paths;
57
58
59 /* Current input file */
60 static const char *g_filename;
61
62 /*
63  * This records all the configuration options seen.
64  * In perl this would be a hash, but here it's a long string
65  * of values separated by newlines.  This is simple and
66  * extremely fast.
67  */
68 char * str_config  = NULL;
69 int    size_config = 0;
70 int    len_config  = 0;
71
72 static void
73 do_depname(void)
74 {
75         if (!hasdep) {
76                 hasdep = 1;
77                 if (g_filename) {
78                         /* Source file (*.[cS]) */
79                         printf("%s:", depname);
80                         printf(" %s", g_filename);
81                 } else {
82                         /* header file (*.h) */
83                         printf("dep_%s +=", depname);
84                 }
85         }
86 }
87
88 /*
89  * Grow the configuration string to a desired length.
90  * Usually the first growth is plenty.
91  */
92 void grow_config(int len)
93 {
94         while (len_config + len > size_config) {
95                 if (size_config == 0)
96                         size_config = 2048;
97                 str_config = realloc(str_config, size_config *= 2);
98                 if (str_config == NULL)
99                         { perror("malloc config"); exit(1); }
100         }
101 }
102
103
104
105 /*
106  * Lookup a value in the configuration string.
107  */
108 int is_defined_config(const char * name, int len)
109 {
110         const char * pconfig;
111         const char * plast = str_config + len_config - len;
112         for ( pconfig = str_config + 1; pconfig < plast; pconfig++ ) {
113                 if (pconfig[ -1] == '\n'
114                 &&  pconfig[len] == '\n'
115                 &&  !memcmp(pconfig, name, len))
116                         return 1;
117         }
118         return 0;
119 }
120
121
122
123 /*
124  * Add a new value to the configuration string.
125  */
126 void define_config(const char * name, int len)
127 {
128         grow_config(len + 1);
129
130         memcpy(str_config+len_config, name, len);
131         len_config += len;
132         str_config[len_config++] = '\n';
133 }
134
135
136
137 /*
138  * Clear the set of configuration strings.
139  */
140 void clear_config(void)
141 {
142         len_config = 0;
143         define_config("", 0);
144 }
145
146
147
148 /*
149  * This records all the precious .h filenames.  No need for a hash,
150  * it's a long string of values enclosed in tab and newline.
151  */
152 char * str_precious  = NULL;
153 int    size_precious = 0;
154 int    len_precious  = 0;
155
156
157
158 /*
159  * Grow the precious string to a desired length.
160  * Usually the first growth is plenty.
161  */
162 void grow_precious(int len)
163 {
164         while (len_precious + len > size_precious) {
165                 if (size_precious == 0)
166                         size_precious = 2048;
167                 str_precious = realloc(str_precious, size_precious *= 2);
168                 if (str_precious == NULL)
169                         { perror("malloc"); exit(1); }
170         }
171 }
172
173
174
175 /*
176  * Add a new value to the precious string.
177  */
178 void define_precious(const char * filename)
179 {
180         int len = strlen(filename);
181         grow_precious(len + 4);
182         *(str_precious+len_precious++) = '\t';
183         memcpy(str_precious+len_precious, filename, len);
184         len_precious += len;
185         memcpy(str_precious+len_precious, " \\\n", 3);
186         len_precious += 3;
187 }
188
189
190
191 /*
192  * Handle an #include line.
193  */
194 void handle_include(int start, const char * name, int len)
195 {
196         struct path_struct *path;
197         int i;
198
199         if (len == 14 && !memcmp(name, "include/config.h", len))
200                 return;
201
202         if (len >= 7 && !memcmp(name, "config/", 7))
203                 define_config(name+7, len-7-2);
204
205         for (i = start, path = path_array+start; i < paths; ++i, ++path) {
206                 memcpy(path->buffer+path->len, name, len);
207                 path->buffer[path->len+len] = '\0';
208                 if (access(path->buffer, F_OK) == 0) {
209                         do_depname();
210                         printf(" \\\n %s $(dep_%s)", path->buffer, path->buffer);
211                         return;
212                 }
213         }
214
215 }
216
217
218
219 /*
220  * Add a path to the list of include paths.
221  */
222 void add_path(const char * name)
223 {
224         struct path_struct *path;
225         char resolved_path[PATH_MAX+1];
226         const char *name2;
227
228         if (strcmp(name, ".")) {
229                 name2 = realpath(name, resolved_path);
230                 if (!name2) {
231                         fprintf(stderr, "realpath(%s) failed, %m\n", name);
232                         exit(1);
233                 }
234         }
235         else {
236                 name2 = "";
237         }
238
239         path_array = realloc(path_array, (++paths)*sizeof(*path_array));
240         if (!path_array) {
241                 fprintf(stderr, "cannot expand path_arry\n");
242                 exit(1);
243         }
244
245         path = path_array+paths-1;
246         path->len = strlen(name2);
247         path->buffer = malloc(path->len+1+256+1);
248         if (!path->buffer) {
249                 fprintf(stderr, "cannot allocate path buffer\n");
250                 exit(1);
251         }
252         strcpy(path->buffer, name2);
253         if (path->len && *(path->buffer+path->len-1) != '/') {
254                 *(path->buffer+path->len) = '/';
255                 *(path->buffer+(++(path->len))) = '\0';
256         }
257 }
258
259
260
261 /*
262  * Record the use of a CONFIG_* word.
263  */
264 void use_config(const char * name, int len)
265 {
266         char *pc;
267         int i;
268
269         pc = path_array[paths-1].buffer + path_array[paths-1].len;
270         memcpy(pc, "config/", 7);
271         pc += 7;
272
273         for (i = 0; i < len; i++) {
274             char c = name[i];
275             if (isupper((int)c)) c = tolower((int)c);
276             if (c == '_')   c = '/';
277             pc[i] = c;
278         }
279         pc[len] = '\0';
280
281         if (is_defined_config(pc, len))
282             return;
283
284         define_config(pc, len);
285
286         do_depname();
287         printf(" \\\n   $(wildcard %s.h)", path_array[paths-1].buffer);
288 }
289
290
291
292 /*
293  * Macros for stunningly fast map-based character access.
294  * __buf is a register which holds the current word of the input.
295  * Thus, there is one memory access per sizeof(unsigned long) characters.
296  */
297
298 #if defined(__alpha__) || defined(__i386__) || defined(__ia64__)  || defined(__x86_64__) || defined(__MIPSEL__) \
299     || defined(__arm__)
300 #define LE_MACHINE
301 #endif
302
303 #ifdef LE_MACHINE
304 #define next_byte(x) (x >>= 8)
305 #define current ((unsigned char) __buf)
306 #else
307 #define next_byte(x) (x <<= 8)
308 #define current (__buf >> 8*(sizeof(unsigned long)-1))
309 #endif
310
311 #define GETNEXT { \
312         next_byte(__buf); \
313         if ((unsigned long) next % sizeof(unsigned long) == 0) { \
314                 if (next >= end) \
315                         break; \
316                 __buf = * (unsigned long *) next; \
317         } \
318         next++; \
319 }
320
321 /*
322  * State machine macros.
323  */
324 #define CASE(c,label) if (current == c) goto label
325 #define NOTCASE(c,label) if (current != c) goto label
326
327 /*
328  * Yet another state machine speedup.
329  */
330 #define MAX2(a,b) ((a)>(b)?(a):(b))
331 #define MIN2(a,b) ((a)<(b)?(a):(b))
332 #define MAX5(a,b,c,d,e) (MAX2(a,MAX2(b,MAX2(c,MAX2(d,e)))))
333 #define MIN5(a,b,c,d,e) (MIN2(a,MIN2(b,MIN2(c,MIN2(d,e)))))
334
335
336
337 /*
338  * The state machine looks for (approximately) these Perl regular expressions:
339  *
340  *    m|\/\*.*?\*\/|
341  *    m|\/\/.*|
342  *    m|'.*?'|
343  *    m|".*?"|
344  *    m|#\s*include\s*"(.*?)"|
345  *    m|#\s*include\s*<(.*?>"|
346  *    m|#\s*(?define|undef)\s*CONFIG_(\w*)|
347  *    m|(?!\w)CONFIG_|
348  *
349  * About 98% of the CPU time is spent here, and most of that is in
350  * the 'start' paragraph.  Because the current characters are
351  * in a register, the start loop usually eats 4 or 8 characters
352  * per memory read.  The MAX5 and MIN5 tests dispose of most
353  * input characters with 1 or 2 comparisons.
354  */
355 void state_machine(const char * map, const char * end)
356 {
357         const char * next = map;
358         const char * map_dot;
359         unsigned long __buf = 0;
360
361         for (;;) {
362 start:
363         GETNEXT
364 __start:
365         if (current > MAX5('/','\'','"','#','C')) goto start;
366         if (current < MIN5('/','\'','"','#','C')) goto start;
367         CASE('/',  slash);
368         CASE('\'', squote);
369         CASE('"',  dquote);
370         CASE('#',  pound);
371         CASE('C',  cee);
372         goto start;
373
374 /* // */
375 slash_slash:
376         GETNEXT
377         CASE('\n', start);
378         NOTCASE('\\', slash_slash);
379         GETNEXT
380         goto slash_slash;
381
382 /* / */
383 slash:
384         GETNEXT
385         CASE('/',  slash_slash);
386         NOTCASE('*', __start);
387 slash_star_dot_star:
388         GETNEXT
389 __slash_star_dot_star:
390         NOTCASE('*', slash_star_dot_star);
391         GETNEXT
392         NOTCASE('/', __slash_star_dot_star);
393         goto start;
394
395 /* '.*?' */
396 squote:
397         GETNEXT
398         CASE('\'', start);
399         NOTCASE('\\', squote);
400         GETNEXT
401         goto squote;
402
403 /* ".*?" */
404 dquote:
405         GETNEXT
406         CASE('"', start);
407         NOTCASE('\\', dquote);
408         GETNEXT
409         goto dquote;
410
411 /* #\s* */
412 pound:
413         GETNEXT
414         CASE(' ',  pound);
415         CASE('\t', pound);
416         CASE('i',  pound_i);
417         CASE('d',  pound_d);
418         CASE('u',  pound_u);
419         goto __start;
420
421 /* #\s*i */
422 pound_i:
423         GETNEXT NOTCASE('n', __start);
424         GETNEXT NOTCASE('c', __start);
425         GETNEXT NOTCASE('l', __start);
426         GETNEXT NOTCASE('u', __start);
427         GETNEXT NOTCASE('d', __start);
428         GETNEXT NOTCASE('e', __start);
429         goto pound_include;
430
431 /* #\s*include\s* */
432 pound_include:
433         GETNEXT
434         CASE(' ',  pound_include);
435         CASE('\t', pound_include);
436         map_dot = next;
437         CASE('"',  pound_include_dquote);
438         CASE('<',  pound_include_langle);
439         goto __start;
440
441 /* #\s*include\s*"(.*)" */
442 pound_include_dquote:
443         GETNEXT
444         CASE('\n', start);
445         NOTCASE('"', pound_include_dquote);
446         handle_include(0, map_dot, next - map_dot - 1);
447         goto start;
448
449 /* #\s*include\s*<(.*)> */
450 pound_include_langle:
451         GETNEXT
452         CASE('\n', start);
453         NOTCASE('>', pound_include_langle);
454         handle_include(1, map_dot, next - map_dot - 1);
455         goto start;
456
457 /* #\s*d */
458 pound_d:
459         GETNEXT NOTCASE('e', __start);
460         GETNEXT NOTCASE('f', __start);
461         GETNEXT NOTCASE('i', __start);
462         GETNEXT NOTCASE('n', __start);
463         GETNEXT NOTCASE('e', __start);
464         goto pound_define_undef;
465
466 /* #\s*u */
467 pound_u:
468         GETNEXT NOTCASE('n', __start);
469         GETNEXT NOTCASE('d', __start);
470         GETNEXT NOTCASE('e', __start);
471         GETNEXT NOTCASE('f', __start);
472         goto pound_define_undef;
473
474 /*
475  * #\s*(define|undef)\s*CONFIG_(\w*)
476  *
477  * this does not define the word, because it could be inside another
478  * conditional (#if 0).  But I do parse the word so that this instance
479  * does not count as a use.  -- mec
480  */
481 pound_define_undef:
482         GETNEXT
483         CASE(' ',  pound_define_undef);
484         CASE('\t', pound_define_undef);
485
486                 NOTCASE('C', __start);
487         GETNEXT NOTCASE('O', __start);
488         GETNEXT NOTCASE('N', __start);
489         GETNEXT NOTCASE('F', __start);
490         GETNEXT NOTCASE('I', __start);
491         GETNEXT NOTCASE('G', __start);
492         GETNEXT NOTCASE('_', __start);
493
494         map_dot = next;
495 pound_define_undef_CONFIG_word:
496         GETNEXT
497         if (isalnum(current) || current == '_')
498                 goto pound_define_undef_CONFIG_word;
499         goto __start;
500
501 /* \<CONFIG_(\w*) */
502 cee:
503         if (next >= map+2 && (isalnum((int)next[-2]) || next[-2] == '_'))
504                 goto start;
505         GETNEXT NOTCASE('O', __start);
506         GETNEXT NOTCASE('N', __start);
507         GETNEXT NOTCASE('F', __start);
508         GETNEXT NOTCASE('I', __start);
509         GETNEXT NOTCASE('G', __start);
510         GETNEXT NOTCASE('_', __start);
511
512         map_dot = next;
513 cee_CONFIG_word:
514         GETNEXT
515         if (isalnum(current) || current == '_')
516                 goto cee_CONFIG_word;
517         use_config(map_dot, next - map_dot - 1);
518         goto __start;
519     }
520 }
521
522
523
524 /*
525  * Generate dependencies for one file.
526  */
527 void do_depend(const char * filename)
528 {
529         int mapsize;
530         int pagesizem1 = getpagesize()-1;
531         int fd;
532         struct stat st;
533         char * map;
534
535         fd = open(filename, O_RDONLY);
536         if (fd < 0) {
537                 perror(filename);
538                 return;
539         }
540
541         fstat(fd, &st);
542         if (st.st_size == 0) {
543                 fprintf(stderr,"%s is empty\n",filename);
544                 close(fd);
545                 return;
546         }
547
548         mapsize = st.st_size;
549         mapsize = (mapsize+pagesizem1) & ~pagesizem1;
550         map = mmap(NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0);
551         if ((long) map == -1) {
552                 perror("mkdep: mmap");
553                 close(fd);
554                 return;
555         }
556         if ((unsigned long) map % sizeof(unsigned long) != 0)
557         {
558                 fprintf(stderr, "do_depend: map not aligned\n");
559                 exit(1);
560         }
561
562         hasdep = 0;
563         clear_config();
564         state_machine(map, map+st.st_size);
565         if (hasdep) {
566                 puts("");
567         }
568
569         munmap(map, mapsize);
570         close(fd);
571 }
572
573
574
575 /*
576  * Generate dependencies for all files.
577  */
578 int main(int argc, char **argv)
579 {
580         int len;
581         const char *hpath;
582
583         hpath = getenv("TOPDIR");
584         if (!hpath) {
585                 fputs("mkdep: TOPDIR not set in environment.  "
586                       "Don't bypass the top level Makefile.\n", stderr);
587                 return 1;
588         }
589
590         add_path(".");          /* for #include "..." */
591
592         while (++argv, --argc > 0) {
593                 if (strncmp(*argv, "-I", 2) == 0) {
594                         if (*((*argv)+2)) {
595                                 add_path((*argv)+2);
596                         }
597                         else {
598                                 ++argv;
599                                 --argc;
600                                 add_path(*argv);
601                         }
602                 }
603                 else if (strcmp(*argv, "--") == 0) {
604                         break;
605                 }
606         }
607
608         add_path(hpath);        /* must be last entry, for config files */
609
610         while (--argc > 0) {
611                 const char * filename = *++argv;
612                 g_filename = 0;
613                 len = strlen(filename);
614                 memcpy(depname, filename, len+1);
615                 if (len > 2 && filename[len-2] == '.') {
616                         if (filename[len-1] == 'c' || filename[len-1] == 'S') {
617                             depname[len-1] = 'o';
618                             g_filename = filename;
619                         }
620                 }
621                 do_depend(filename);
622         }
623         if (len_precious) {
624                 *(str_precious+len_precious) = '\0';
625                 printf(".PRECIOUS:%s\n", str_precious);
626         }
627         return 0;
628 }