src/build.c

   1 /* build.c -- main file of the Build.
   2
   3    Copyright (C) 2022 Sergey Sushilin <sergeysushilin@protonmail.com>
   4
   5    This file is part of Build.
   6
   7    Build is free software: you can redistribute it and/or
   8    modify it under the terms of either the GNU General Public License
   9    as published by the Free Software Foundation;
  10    either version 2 of the License, or version 3 of the License,
  11    or both in parallel, as here.
  12
  13    Build is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received copies of the GNU General Public License
  19    version 2 and 3 along with this program.
  20    If not, see http://www.gnu.org/licenses/.  */
  21
  22 #include <errno.h>
  23 #include <locale.h>
  24 #include <stdint.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 #if defined (__FreeBSD__) || defined (__OpenBSD__) || defined (__NetBSD__)
  30 # define __BSD_VISIBLE 1
  31 # include <sys/types.h>
  32 # include <sys/sysctl.h>
  33 #endif
  34
  35 #ifndef _WIN32
  36 # include <unistd.h>
  37 #endif
  38
  39 #include "build.h"
  40 //#include "depfile-scan.h"
  41 #include "diagnostic.h"
  42 #include "graph.h"
  43 #include "job-server.h"
  44 #include "option.h"
  45 #include "parse.h"
  46 #include "scan.h"
  47 #include "sh.h"
  48 #include "spawn.h"
  49 #include "thread.h"
  50 #include "utils.h"
  51 #include "watchdog.h"
  52
  53 bool
  54 variable_create (Hash *variables, uniqstr name, struct uniqstr_array *strings)
  55 {
  56   struct variable *variable;
  57
  58   if (UNLIKELY (STRLITEQ (name, "in")
  59              || STRLITEQ (name, "out")
  60              || STRLITEQ (name, "target")
  61              || STRLITEQ (name, "dependencies")
  62              || STRLITEQ (name, "files")))
  63     {
  64       error (_("%s: this variable name is reserved"), name);
  65       return false;
  66     }
  67
  68   variable = xmalloc (sizeof (*variable));
  69   variable->name = name;
  70   variable->value = *strings;
  71   HashInsert (variables, name, uniqstr_len (name), variable);
  72   return true;
  73 }
  74
  75 static inline bool
  76 variable_lookup (const Hash *variables, uniqstr name,
  77                  const struct variable **v)
  78 {
  79   const struct variable *variable = HashFind (variables, name, uniqstr_len (name));
  80
  81   if (LIKELY (variable != NULL))
  82     {
  83       *v = variable;
  84       return true;
  85     }
  86
  87   error (_("variable %s is not defined"), name);
  88   return false;
  89 }
  90
  91 static void
  92 variable_destroy (void *p)
  93 {
  94   struct variable *variable = p;
  95
  96   free (variable->value.array);
  97   free (variable);
  98 }
  99
 100 static inline void NONNULL (1, 2)
 101 variables_duplicate (Hash *dst, const Hash *src)
 102 {
 103   HashInit (dst);
 104
 105   for (HashElem *p = HashFirst (src); p != NULL; p = HashNext (p))
 106     {
 107       const struct variable *v = p->data;
 108       struct variable *variable = xmalloc (sizeof (*variable));
 109
 110       variable->name = v->name;
 111       variable->value.count = v->value.count;
 112       variable->value.array = xmallocarray (variable->value.count,
 113                                             sizeof (*variable->value.array));
 114
 115       for (size_t i = 0; i < variable->value.count; i++)
 116         variable->value.array[i] = v->value.array[i];
 117
 118       HashInsert (dst, HashKeyPtr (p), HashKeySize (p), variable);
 119     }
 120 }
 121
 122 bool
 123 target_create (struct target **t,
 124                Hash *targets,
 125                uniqstr name,
 126                struct target_skeleton *skeleton)
 127 {
 128   if (UNLIKELY (HashFind (targets, name, uniqstr_len (name)) != NULL))
 129     {
 130       error (_("redefinition of target %s"), name);
 131       return false;
 132     }
 133
 134   if (skeleton->files.count != 0 && skeleton->apply_rules.count == 0)
 135     {
 136       error (_("target %s depends on files, but no rules provided"), name);
 137       return false;
 138     }
 139
 140   struct target *target = xmalloc (sizeof (*target));
 141
 142   target->name = name;
 143   target->skeleton = skeleton;
 144
 145   HashInsert (targets, name, uniqstr_len (name), target);
 146
 147   if (t != NULL)
 148     *t = target;
 149
 150   return true;
 151 }
 152
 153 static void
 154 target_skeleton_destroy (void *p)
 155 {
 156   return;//TODO
 157   struct target_skeleton *skeleton = p;
 158
 159   free (skeleton->dependencies.array);
 160   free (skeleton->files.array);
 161   free (skeleton->apply_rules.array);
 162   free (skeleton);
 163 }
 164
 165 static void rule_destroy (void *p);
 166
 167 bool
 168 rule_create (Hash *rules, uniqstr name, uniqstr description,
 169              struct uniqstr_array *commands, const Hash *variables)
 170 {
 171   if (UNLIKELY (HashFind (rules, name, uniqstr_len (name)) != NULL))
 172     {
 173       error (_("redefinition of rule %s"), name);
 174       return false;
 175     }
 176
 177   struct rule *rule = xmalloc (sizeof (*rule));
 178
 179   rule->name = name;
 180   rule->description = description;
 181   rule->commands = *commands;
 182   variables_duplicate (&rule->variables, variables);
 183   HashInsert (rules, name, uniqstr_len (name), rule);
 184   return true;
 185 }
 186
 187 static void
 188 rule_destroy (void *p)
 189 {
 190   struct rule *rule = p;
 191
 192   free (rule->commands.array);
 193   HashClearWithDestructor (&rule->variables, variable_destroy);
 194   free (rule);
 195 }
 196
 197 static inline bool
 198 is_name_character (char c)
 199 {
 200 #if '@' == 0x40 /* ASCII character set.  */
 201 # define TAG(c) \
 202   ((uint64_t) 1 << (c % BITSIZE))
 203
 204   enum { BITSIZE = 8 * sizeof (uint64_t) };
 205   const uint64_t name_characters[256 / BITSIZE] =
 206     {
 207       /* 45 */
 208         TAG ('-')
 209       /* 48-57 */
 210       | TAG ('0')
 211       | TAG ('1')
 212       | TAG ('2')
 213       | TAG ('3')
 214       | TAG ('4')
 215       | TAG ('5')
 216       | TAG ('6')
 217       | TAG ('7')
 218       | TAG ('8')
 219       | TAG ('9'),
 220         /* 64-90 */
 221         TAG ('A')
 222       | TAG ('B')
 223       | TAG ('C')
 224       | TAG ('D')
 225       | TAG ('E')
 226       | TAG ('F')
 227       | TAG ('G')
 228       | TAG ('H')
 229       | TAG ('I')
 230       | TAG ('J')
 231       | TAG ('K')
 232       | TAG ('L')
 233       | TAG ('M')
 234       | TAG ('N')
 235       | TAG ('O')
 236       | TAG ('P')
 237       | TAG ('Q')
 238       | TAG ('R')
 239       | TAG ('S')
 240       | TAG ('T')
 241       | TAG ('U')
 242       | TAG ('V')
 243       | TAG ('W')
 244       | TAG ('X')
 245       | TAG ('Y')
 246       | TAG ('Z')
 247         /* 95 */
 248       | TAG ('_')
 249         /* 97-122 */
 250       | TAG ('a')
 251       | TAG ('b')
 252       | TAG ('c')
 253       | TAG ('d')
 254       | TAG ('e')
 255       | TAG ('f')
 256       | TAG ('g')
 257       | TAG ('h')
 258       | TAG ('i')
 259       | TAG ('j')
 260       | TAG ('k')
 261       | TAG ('l')
 262       | TAG ('m')
 263       | TAG ('n')
 264       | TAG ('o')
 265       | TAG ('p')
 266       | TAG ('q')
 267       | TAG ('r')
 268       | TAG ('s')
 269       | TAG ('t')
 270       | TAG ('u')
 271       | TAG ('v')
 272       | TAG ('w')
 273       | TAG ('x')
 274       | TAG ('y')
 275       | TAG ('z')
 276     };
 277 # undef TAG
 278   const unsigned char uc = *(unsigned char *) &c;
 279
 280   return name_characters[uc / BITSIZE] & ((uint64_t) 1 << (uc % BITSIZE));
 281 #else
 282   return (c >= 'a' && c <= 'z')
 283       || (c >= 'A' && c <= 'Z')
 284       || (c >= '0' && c <= '9')
 285       || (c == '-' || c == '_');
 286 #endif
 287 }
 288
 289 #if 0
 290 static inline NODISCARD bool
 291 argv_append (unsigned int *restrict arga,
 292              unsigned int *restrict argc,
 293              uniqstr **argv,
 294              uniqstr arg)
 295 {
 296   unsigned int a = *arga;
 297   unsigned int c = *argc;
 298   uniqstr *v = *argv;
 299
 300   if (UNLIKELY (c >= a - 1))
 301     {
 302       v = xreallocarray (v, 2 * a, sizeof (*v));
 303       *arga = 2 * a;
 304     }
 305
 306   v[c++] = arg;
 307   v[c] = NULL;
 308   *argc = c;
 309   *argv = v;
 310   return true;
 311 }
 312
 313 static inline void
 314 argv_free (uniqstr *argv)
 315 {
 316   free (argv);
 317 }
 318
 319 static inline bool
 320 ascii_isspace (char c)
 321 {
 322   /* Make sure that characters have appropriate ASCII numbers.  */
 323 #if !(' '  == 0x20 \
 324    && '\t' == 0x09 \
 325    && '\n' == 0x0A \
 326    && '\v' == 0x0B \
 327    && '\f' == 0x0C \
 328    && '\r' == 0x0D)
 329   switch (c)
 330     {
 331     case ' ':
 332     case '\t':
 333     case '\f':
 334     case '\n':
 335     case '\r':
 336     case '\v':
 337       return true;
 338     default:
 339       return false;
 340     }
 341 #else
 342   const uint64_t spaces[256 / sizeof (uint64_t)] =
 343     {
 344       ((uint64_t) 1 << '\t')
 345     | ((uint64_t) 1 << '\f')
 346     | ((uint64_t) 1 << '\n')
 347     | ((uint64_t) 1 << '\r')
 348     | ((uint64_t) 1 << '\v')
 349     | ((uint64_t) 1 << ' '),
 350     };
 351   const unsigned char uc = *(unsigned char *) &c;
 352   enum { BITSIZE = 8 * sizeof (uint64_t) };
 353
 354   return spaces[uc / BITSIZE] & ((uint64_t) 1 << (uc % BITSIZE));
 355 #endif
 356 }
 357
 358 static inline NODISCARD bool
 359 parse_command (uniqstr command,
 360                const Hash *variables,
 361                unsigned int *count,
 362                uniqstr **vector)
 363 {
 364   char *arg;
 365   char *buffer;
 366   bool dquote = false;
 367   unsigned int argc = 0;
 368   unsigned int arga = 8;
 369   uniqstr *argv;
 370   size_t i = 0;
 371
 372   argv = xmalloc (arga * sizeof (*argv));
 373   buffer = xmalloc (uniqstr_len (command) + 1);
 374
 375   /* Is a do-while to always execute the loop once.  Always return an
 376      argv, even for null strings.  */
 377   do
 378     {
 379       while (ascii_isspace (command[i]))
 380         i++;
 381
 382       /* Begin scanning argument.  */
 383       arg = buffer;
 384
 385       while (command[i] != '\0')
 386         {
 387           if (UNLIKELY (ascii_isspace (command[i]) && !dquote))
 388             break;
 389
 390           dquote ^= (command[i] == '"');
 391
 392           if (command[i] == '@')
 393             {
 394               bool begins_by_curly_bracked = (command[i + 1] == '{');
 395
 396               if (!is_name_character (command[i + 1])
 397                && !begins_by_curly_bracked)
 398                 {
 399                   error (_("expected variable name"));
 400                   goto lfail;
 401                 }
 402
 403               size_t len = 1;
 404               uniqstr name;
 405               const struct variable *variable;
 406
 407               i++;
 408
 409               while (command[i + len] != '\0')
 410                 {
 411                   if ((begins_by_curly_bracked && command[i + len] == '}')
 412                    || ascii_isspace (command[i + len]))
 413                     break;
 414
 415                   if (!is_name_character (command[i + len]))
 416                     {
 417                       if (begins_by_curly_bracked)
 418                         error (_("expected '}', but got '%c'"),
 419                                command[i + len]);
 420                       else
 421                         break;
 422
 423                       goto lfail;
 424                     }
 425
 426                   len++;
 427                 }
 428
 429               name = uniqstr_new_from_buffer (command + i + begins_by_curly_bracked, len - begins_by_curly_bracked);
 430
 431               if (UNLIKELY (!variable_lookup (variables, name, &variable)))
 432                 goto lfail;
 433
 434               if (begins_by_curly_bracked && variable->value.count != 1)
 435                 {
 436                   error (_("can not use curly brackets with multi-string variable"));
 437                   goto lfail;
 438                 }
 439
 440               for (size_t j = 0; j < variable->value.count; j++)
 441                 if (UNLIKELY (!argv_append (&arga, &argc, &argv,
 442                                             variable->value.array[j])))
 443                   goto lfail;
 444
 445               i += len + begins_by_curly_bracked;
 446               goto lskip;
 447             }
 448           else
 449             *arg++ = command[i];
 450
 451           i++;
 452         }
 453
 454       *arg = '\0';
 455
 456       if (UNLIKELY (!argv_append (&arga, &argc, &argv, uniqstr_new (buffer))))
 457         goto lfail;
 458
 459     lskip:
 460       while (ascii_isspace (command[i]))
 461         i++;
 462     }
 463   while (command[i] != '\0');
 464
 465   free (buffer);
 466   *count = argc;
 467   *vector = argv;
 468   return true;
 469
 470 lfail:
 471   free (buffer);
 472   argv_free (argv);
 473   return false;
 474 }
 475 #endif
 476
 477 static inline NODISCARD bool
 478 parse_description (const uniqstr description,
 479                    const Hash *variables,
 480                    char **result)
 481 {
 482   size_t slen = uniqstr_len (description);
 483   uniqstr d = description;
 484   size_t written = 0;
 485   char *s = xmalloc (slen + 1);
 486
 487   while (d[0] != '\0')
 488     {
 489       if (d[0] == '@' && is_name_character (d[1]))
 490         {
 491           size_t len = 2;
 492           uniqstr name;
 493           const struct variable *variable;
 494
 495           while (is_name_character (d[len]))
 496             len++;
 497
 498           name = uniqstr_new_from_buffer (d + 1, len - 1);
 499
 500           if (UNLIKELY (!variable_lookup (variables, name, &variable)))
 501             goto lfail;
 502
 503           for (size_t i = 0; i < variable->value.count; i++)
 504             slen += uniqstr_len (variable->value.array[i]) + 1;
 505
 506           s = xrealloc (s, slen + 1);
 507
 508           for (size_t i = 0; i < variable->value.count; i++)
 509             {
 510               memcpy (s + written, variable->value.array[i],
 511                       uniqstr_len (variable->value.array[i]));
 512               written += uniqstr_len (variable->value.array[i]);
 513               s[written++] = ' ';
 514             }
 515
 516           written--;
 517           d += len;
 518           continue;
 519         }
 520
 521       s[written++] = *d++;
 522     }
 523
 524   s[written] = '\0';
 525   *result = s;
 526   return true;
 527
 528 lfail:
 529   free (s);
 530   return false;
 531 }
 532
 533 #if 0 //TODO
 534 static char *substitude_variables (uniqstr command, const Hash *variables,
 535                                    struct quoting_slots *qs)
 536 {
 537   return command;
 538   size_t length = 0;
 539   size_t size = uniqstr_len (command) + 1;
 540   char *result = xmalloc (size);
 541   size_t rest_length = uniqstr_len (command);
 542   const char *cur = command;
 543   const char *prv = command;
 544   const char *const end = command + rest_length;
 545
 546   while ((cur = memchr (cur, '@', rest_length)) != NULL)
 547     {
 548       if (cur != prv)
 549         {
 550           memcpy (result + length, prv, (size_t) (cur - prv));
 551           length += (size_t) (cur - prv);
 552         }
 553
 554       cur++;
 555
 556       size_t variable_name_length = 0;
 557
 558       for (size_t i = 0; is_name_character (cur[i]); i++)
 559         variable_name_length++;
 560
 561       uniqstr name = uniqstr_new_from_buffer (cur, variable_name_length);
 562       struct variable *variable = HashFind (variables, name, uniqstr_len (name));
 563
 564       if (UNLIKELY (variable == NULL))
 565         {
 566           error (_("variable is not declared: %s"),
 567                  quote (qs, name));
 568           return NULL;
 569         }
 570
 571       struct uniqstr_array *value = &variable->value;
 572       size_t add_size = 0;
 573
 574       for (size_t i = 0; i < value->count; i++)
 575         add_size += (uniqstr_len (value->array[i]) + ((i != value->count - 1) ? 1 : 0));
 576
 577       size += add_size;
 578       size -= variable_name_length + 1;
 579       result = xrealloc (result, size);
 580
 581       for (size_t i = 0; i < value->count; i++)
 582         {
 583           memcpy (result + length, value->array[i],
 584                   uniqstr_len (value->array[i]));
 585           length += uniqstr_len (value->array[i]);
 586
 587           if (i != value->count - 1)
 588             result[length++] = ' ';
 589         }
 590
 591       cur+=variable_name_length;
 592       rest_length -= (size_t) (cur - prv);
 593       prv = cur;
 594     }
 595
 596   if (prv != end)
 597     {
 598       memcpy (result + length, prv, (size_t) (end - prv));
 599       length += (size_t) (end - prv);
 600     }
 601
 602   puts (result);
 603   return result;
 604 }
 605 #endif
 606
 607 static inline NODISCARD bool NONNULL (2, 3, 4)
 608 command_execute (uniqstr description,
 609                  uniqstr command,
 610                  const Hash *variables,
 611                  struct quoting_slots *qs,
 612                  char **envp,
 613                  bool dryrun)
 614 {
 615   //TODOunsigned int argc;
 616   //uniqstr *argv;
 617
 618   if (description == NULL)
 619     {
 620       /*TODO
 621       for (unsigned int j = 0; j < argc; j++)
 622         {
 623           fputs (argv[j], stdout);
 624
 625           if (j != argc - 1)
 626             fputc (' ', stdout);
 627         }
 628
 629       fputc ('\n', stdout);*/
 630       puts (command);
 631     }
 632   else
 633     {
 634       char *desc;
 635
 636       if (LIKELY (parse_description (description, variables, &desc)))
 637         {
 638           puts (desc);
 639           free (desc);
 640         }
 641       else
 642         warning (_("%s: failed to parse rule description"), quote (qs, description));
 643     }
 644
 645 #if 0
 646   if (UNLIKELY (!parse_command (command, variables, &argc, &argv)))
 647     return false;
 648
 649   if (!dryrun && spawn_process (argv, envp) != SPAWN_SUCCESS)
 650     {
 651       error (_("%s: failed to execute"), quotef (qs, argv[0]));
 652       argv_free (argv);
 653       return false;
 654     }
 655
 656   argv_free (argv);
 657 #else
 658   command_t *root = NULL;
 659
 660   if (!bsh_parse_line (/* substitude_variables (command, variables, qs) */command, &root, variables))
 661     return false;
 662
 663   if (!dryrun && root != NULL && bsh_parse_command (root, NULL) != 0)
 664     return false;
 665 #endif
 666
 667   return true;
 668 }
 669
 670 static inline NODISCARD bool NONNULL (1, 2, 3)
 671 rule_apply (const struct apply_rule *apply_rule,
 672             const Hash *rules,
 673             struct quoting_slots *qs,
 674             char **envp,
 675             bool dryrun)
 676 {
 677   Hash variables;
 678   struct variable in = { 0 };
 679   struct variable out = { 0 };
 680   struct rule *r = HashFind (rules, apply_rule->name, uniqstr_len (apply_rule->name));
 681   uniqstr out_array[1] = { 0 };
 682
 683   if (UNLIKELY (r == NULL))
 684     {
 685       error (_("can not find rule %s"), quote (qs, apply_rule->name));
 686       return false;
 687     }
 688
 689   variables_duplicate (&variables, &r->variables);
 690
 691   if (LIKELY (apply_rule->in.count != 0))
 692     {
 693       in.name = uniqstr_new_from_literal_string ("in");
 694       in.value.count = apply_rule->in.count;
 695       in.value.array = apply_rule->in.array;
 696       HashInsert (&variables, in.name, uniqstr_len (in.name), &in);
 697     }
 698
 699   if (LIKELY (apply_rule->out != NULL))
 700     {
 701       out_array[0] = (uniqstr) apply_rule->out;
 702       out.name = uniqstr_new_from_literal_string ("out");
 703       out.value.count = 1;
 704       out.value.array = out_array;
 705       HashInsert (&variables, out.name, uniqstr_len (out.name), &out);
 706     }
 707
 708   bool status = true;
 709
 710   for (size_t i = 0; i < r->commands.count; i++)
 711     if (UNLIKELY (!command_execute (r->description, r->commands.array[i],
 712                                     &variables, qs, envp, dryrun)))
 713       {
 714         status = false;
 715         break;
 716       }
 717
 718   if (LIKELY (apply_rule->in.count != 0))
 719     HashRemove (&variables, in.name, uniqstr_len (in.name));
 720
 721   if (LIKELY (apply_rule->out != NULL))
 722     HashRemove (&variables, out.name, uniqstr_len (out.name));
 723
 724   HashClearWithDestructor (&variables, variable_destroy);
 725   return status;
 726 }
 727
 728 #if 0 //TODO
 729 static inline NODISCARD bool
 730 pattern_target_match (uniqstr target_name, uniqstr name, uniqstr *percent)
 731 {
 732   const char *p = uniqstr_chr (target_name, '%');
 733   const size_t start_len = (size_t) (p - target_name);
 734   const size_t finish_len = (size_t) (target_name + uniqstr_len (target_name) - p - 1);
 735
 736   /* Always non-null.  */
 737   if (uniqstr_len (name) < (start_len + finish_len + 1))
 738     return false;
 739
 740   if (start_len != 0 && memcmp (name, target_name, start_len) != 0)
 741     return false;
 742
 743   if (finish_len != 0 && memcmp (name + uniqstr_len (name) - finish_len, target_name + uniqstr_len (target_name) - finish_len, finish_len) != 0)
 744     return false;
 745
 746   *percent = uniqstr_new_from_buffer (name + start_len, uniqstr_len (name) - (start_len + finish_len));
 747   return true;
 748 }
 749
 750 static inline NODISCARD size_t PURE
 751 percent_count (uniqstr s)
 752 {
 753   size_t count = 0;
 754   size_t n = uniqstr_len (s);
 755
 756   for (const char *p = s; (s = memchr (s, '%', n)) != NULL; p = s)
 757     {
 758       s++;
 759       n -= (size_t) (s - p);
 760       count++;
 761     }
 762
 763   return count;
 764 }
 765
 766 static inline NODISCARD uniqstr
 767 replace_percents (uniqstr src, uniqstr percent)
 768 {
 769   uniqstr s;
 770   size_t count = percent_count (src);
 771
 772   if (count == 0)
 773     return src;
 774
 775   char *const base = uniqstr_prepare (count * uniqstr_len (percent) + uniqstr_len (src) - 1);
 776   char *r = base;
 777   const char *prv = src;
 778   const char *cur = src;
 779   size_t len = uniqstr_len (src);
 780   const char *const end = src + len;
 781
 782   while ((cur = memchr (cur, '%', len)) != NULL)
 783     {
 784       if (cur != prv)
 785         {
 786           memcpy (r, prv, (size_t) (cur - prv));
 787           r += (cur - prv);
 788         }
 789
 790       memcpy (r, percent, uniqstr_len (percent));
 791       r += uniqstr_len (percent);
 792       cur++;
 793       len -= (size_t) (cur - prv);
 794       prv = cur;
 795     }
 796
 797   if (prv != end)
 798     {
 799       memcpy (r, prv, (size_t) (end - prv));
 800       r += (end - prv);
 801     }
 802
 803   *r = '\0';
 804   s = uniqstr_finish_preparation (base);
 805   return s;
 806 }
 807 #endif
 808
 809 struct target_skeleton *
 810 target_skeleton_create (Hash *skeletons,
 811                         struct uniqstr_array *dependencies,
 812                         struct uniqstr_array *files,
 813                         struct uniqstr_array *outfiles,
 814                         struct apply_rule_array *apply_rules)
 815 {
 816   struct target_skeleton *skeleton = xmalloc (sizeof (*skeleton));
 817
 818   skeleton->dependencies = *dependencies;
 819   skeleton->files = *files;
 820   skeleton->outfiles = *outfiles;
 821   skeleton->apply_rules = *apply_rules;
 822   atomic_init (&skeleton->need_rebuild, false);
 823   HashInsert (skeletons, skeleton, sizeof (*skeleton), skeleton);
 824   return skeleton;
 825 }
 826
 827 /*
 828 static inline NODISCARD struct target * NONNULL (1, 2)
 829 target_create_from_pattern_target (Hash *targets,
 830                                    const struct target *pattern_target,
 831                                    uniqstr percent)
 832 {
 833 #define ARRAY_DUPLICATE(a0, a1)                                         \
 834   do                                                                    \
 835     {                                                                   \
 836       if (LIKELY ((a1).count != 0))                                     \
 837         {                                                               \
 838           (a0).count = (a1).count;                                      \
 839           (a0).array = xmallocarray ((a0).count, sizeof (*(a0).array)); \
 840                                                                         \
 841           for (size_t __i = 0; __i < (a0).count; __i++)                 \
 842             (a0).array[__i] = replace_percents ((a1).array[__i],        \
 843                                                 percent);               \
 844         }                                                               \
 845     }                                                                   \
 846   while (0)
 847
 848   struct target *t;
 849   uniqstr name;
 850   struct uniqstr_array dependencies = { 0 };
 851   struct uniqstr_array files = { 0 };
 852   struct uniqstr_array outfiles = { 0 };
 853   struct apply_rule_array apply_rules = { 0 };
 854
 855   name = replace_percents (pattern_target->name, percent);
 856   ARRAY_DUPLICATE (dependencies, pattern_target->skeleton->dependencies);
 857   ARRAY_DUPLICATE (files, pattern_target->skeleton->files);
 858   ARRAY_DUPLICATE (outfiles, pattern_target->skeleton->outfiles);
 859
 860   if (LIKELY (pattern_target->skeleton->apply_rules.count != 0))
 861     {
 862       apply_rules.count = pattern_target->skeleton->apply_rules.count;
 863       apply_rules.array = xmallocarray (apply_rules.count, sizeof (*apply_rules.array));
 864
 865       for (size_t i = 0; i < pattern_target->skeleton->apply_rules.count; i++)
 866         {
 867           apply_rules.array[i].name = pattern_target->skeleton->apply_rules.array[i].name;
 868
 869           if (LIKELY (pattern_target->skeleton->apply_rules.array[i].in.count != 0))
 870             ARRAY_DUPLICATE (apply_rules.array[i].in, pattern_target->skeleton->apply_rules.array[i].in);
 871
 872           if (LIKELY (pattern_target->skeleton->apply_rules.array[i].out != NULL))
 873             apply_rules.array[i].out = replace_percents (pattern_target->skeleton->apply_rules.array[i].out, percent);
 874           else
 875             apply_rules.array[i].out = NULL;
 876         }
 877     }
 878
 879   struct target_skeleton *skeleton = target_skeleton_create (&dependencies,
 880                                                              &files,
 881                                                              &outfiles,
 882                                                              &apply_rules);
 883
 884   if (LIKELY (target_create (&t, targets, name, skeleton)))
 885     return t;
 886
 887   return NULL;
 888 #undef ARRAY_DUPLICATE
 889 }
 890 */
 891
 892 static NODISCARD struct target * NONNULL (1, 2)
 893 target_find (const Hash *targets, uniqstr name)
 894 {
 895   return HashFind (targets, name, uniqstr_len (name));
 896 }
 897
 898 static NODISCARD bool NONNULL (1, 2, 3, 4, 6, 7, 8, 9)
 899 build_tree_create (struct build_tree *root,
 900                    struct build_tree_branch **pbranch,
 901                    const Hash *restrict targets,
 902                    Hash *restrict branches,
 903                    bool rebuild,
 904                    uniqstr target_name,
 905                    struct watchdog *wd,
 906                    struct quoting_slots *qs,
 907                    struct Hash *restrict table_for_loop_detection,
 908                    struct Hash *restrict tracked_files)
 909 {
 910   struct target *target = target_find (targets, target_name);
 911
 912   if (UNLIKELY (target == NULL))
 913     {
 914       error (_("there is no %s target"), quote (qs, target_name));
 915       return false;
 916     }
 917
 918   if (UNLIKELY (HashFind (table_for_loop_detection,
 919                           target->name,
 920                           uniqstr_len (target->name)) != NULL))
 921     {
 922       error (_("dependence loop detected: %s depends on itself"),
 923              quote (qs, target_name));
 924       return false;
 925     }
 926
 927   HashInsert (table_for_loop_detection, target->name,
 928               uniqstr_len (target->name), target);
 929
 930   struct build_tree_branch *branch = HashFind (branches, target->name,
 931                                                uniqstr_len (target->name));
 932
 933   if (branch == NULL)
 934     {
 935       branch = xmalloc (sizeof (*branch));
 936       branch->target = target;
 937
 938       if (LIKELY (target->skeleton->dependencies.count != 0))
 939         {
 940           branch->branches.count = target->skeleton->dependencies.count;
 941           branch->branches.array = xmallocarray (branch->branches.count, sizeof (*branch->branches.array));
 942
 943           for (size_t i = 0; i < target->skeleton->dependencies.count; i++)
 944             {
 945               if (UNLIKELY (!build_tree_create (root,
 946                                                 &branch->branches.array[i],
 947                                                 targets,
 948                                                 branches,
 949                                                 rebuild,
 950                                                 target->skeleton->dependencies.array[i],
 951                                                 wd, qs, table_for_loop_detection,
 952                                                 tracked_files)))
 953                 return false;
 954
 955               target->skeleton->need_rebuild |= branch->branches.array[i]->target->skeleton->need_rebuild;
 956             }
 957         }
 958       else
 959         {
 960           branch->branches.count = 0;
 961           branch->branches.array = NULL;
 962         }
 963
 964       for (size_t i = 0; i < target->skeleton->files.count; i++)
 965         {
 966           if (target_find (targets, target->skeleton->files.array[i]) != NULL)
 967             {
 968               branch->branches.array = xreallocarray (branch->branches.array, (branch->branches.count + 1),
 969                                                       sizeof (*branch->branches.array));
 970
 971               if (UNLIKELY (!build_tree_create (root,
 972                                                 &branch->branches.array[branch->branches.count],
 973                                                 targets,
 974                                                 branches,
 975                                                 rebuild,
 976                                                 target->skeleton->files.array[i],
 977                                                 wd, qs, table_for_loop_detection,
 978                                                 tracked_files)))
 979                 return false;
 980
 981               target->skeleton->need_rebuild |= branch->branches.array[branch->branches.count]->target->skeleton->need_rebuild;
 982               branch->branches.count++;
 983             }
 984         }
 985
 986       target->skeleton->need_rebuild |= rebuild;
 987
 988       for (size_t i = 0; i < target->skeleton->files.count; i++)
 989         target->skeleton->need_rebuild |= watchdog_track_file (wd, tracked_files, target->skeleton->files.array[i], qs);
 990
 991       for (size_t i = 0; !target->skeleton->need_rebuild && i < target->skeleton->outfiles.count; i++)
 992         target->skeleton->need_rebuild |= (access (target->skeleton->outfiles.array[i], F_OK) != 0);
 993
 994       root->count_of_targets++;
 995       HashInsert (branches, target->name, uniqstr_len (target->name), branch);
 996     }
 997
 998   HashRemove (table_for_loop_detection, target->name, uniqstr_len (target->name));
 999   *pbranch = branch;
1000   return true;
1001 }
1002
1003 static NODISCARD bool NONNULL (1, 2, 3)
1004 build (const struct build_tree_branch *branch,
1005        const Hash *rules,
1006        struct quoting_slots *qs,
1007        char **envp,
1008        bool dryrun)
1009 {
1010   for (size_t i = 0; i < branch->target->skeleton->apply_rules.count; i++)
1011     if (UNLIKELY (!rule_apply (&branch->target->skeleton->apply_rules.array[i], rules, qs, envp, dryrun)))
1012       return false;
1013
1014   for (size_t i = 0; i < branch->target->skeleton->outfiles.count; i++)
1015     if (access (branch->target->skeleton->outfiles.array[i], F_OK) != 0)
1016       {
1017         error (_("target %s must have created file %s"),
1018                quote_n (qs, 0, branch->target->name),
1019                quote_n (qs, 1, branch->target->skeleton->outfiles.array[i]));
1020         return false;
1021       }
1022
1023   branch->target->skeleton->need_rebuild = false;
1024   return true;
1025 }
1026
1027 static bool
1028 build_target (const struct build_tree_branch *branch,
1029               const Hash *restrict rules,
1030               struct quoting_slots *qs,
1031               char **envp,
1032               const Hash *restrict tracked_files,
1033               bool dryrun)
1034 {
1035   bool status = true;
1036   bool need_rebuild = branch->target->skeleton->need_rebuild;
1037
1038   for (size_t i = 0; i < branch->target->skeleton->files.count; i++)
1039     need_rebuild |= watchdog_file_updated (tracked_files, branch->target->skeleton->files.array[i], qs);
1040
1041   if (!need_rebuild)
1042     {
1043       info (_("nothing to be done for %s"), quote (qs, branch->target->name));
1044       status = true;
1045     }
1046   else
1047     {
1048       if (LIKELY (build (branch, rules, qs, envp, dryrun)))
1049         {
1050           /* Do not inform about targets with no rules.  */
1051           if (branch->target->skeleton->apply_rules.count != 0)
1052             info (_("%s: was successfully built"),
1053                   quote (qs, branch->target->name));
1054
1055           status = true;
1056         }
1057       else
1058         {
1059           error (_("%s: building failed"), quote (qs, branch->target->name));
1060           status = false;
1061         }
1062     }
1063
1064   return status;
1065 }
1066
1067 static NODISCARD bool NONNULL (1, 2, 3)
1068 build_tree_traverse (struct build_tree *tree,
1069                      const Hash *restrict rules,
1070                      char **envp,
1071                      const Hash *restrict tracked_files,
1072                      bool dryrun,
1073                      size_t n_cores)
1074 {
1075   struct job_server job_server;
1076   bool status = true;
1077
1078   if (tree->count_of_targets == 0)
1079     return true;
1080
1081   if (!job_server_initialize (&job_server, build_target, n_cores * 2,
1082                               rules, envp, tracked_files, dryrun))
1083     return false;
1084
1085   if (!job_list_create_from_build_tree (&job_server.job_list, tree))
1086     return false;
1087
1088   status &= job_server_start (&job_server);
1089   status &= job_server_finalize (&job_server);
1090   return status;
1091 }
1092
1093 static void
1094 build_tree_branch_destroy (struct build_tree_branch *branch)
1095 {
1096   for (size_t i = 0; i < branch->branches.count; i++)
1097     build_tree_branch_destroy (branch->branches.array[i]);
1098
1099   if (branch->branches.count != 0)
1100     {
1101       free (branch->branches.array);
1102       branch->branches.count = 0;
1103     }
1104
1105   //TODO  free (branch);
1106 }
1107
1108 static void
1109 build_tree_destroy (struct build_tree *tree)
1110 {
1111   build_tree_branch_destroy (tree->root);
1112   //TODO  free (tree->root);
1113 }
1114
1115 static inline NODISCARD size_t
1116 get_count_of_processor_cores (void)
1117 {
1118 #if defined (__linux__)
1119   long n_cores = sysconf (_SC_NPROCESSORS_ONLN);
1120
1121   return (n_cores < 1) ? 1 : (size_t) n_cores;
1122 #elif defined (__FreeBSD__) || defined (__OpenBSD__) || defined (__NetBSD__)
1123   int mib[4];
1124   int n_cores;
1125   size_t size = sizeof (n_cores);
1126
1127   /* Set the mib for hw.ncpu.  */
1128   mib[0] = CTL_HW;
1129   mib[1] = HW_NCPU;
1130
1131   /* Get the number of CPUs from the system.  */
1132   sysctl (mib, 2, &n_cores, &size, NULL, 0);
1133
1134   return (n_cores < 1) ? 1 : (size_t) n_cores;
1135 #elif defined (_WIN32)
1136   SYSTEM_INFO sysinfo;
1137   DWORD n_cores;
1138
1139   GetSystemInfo (&sysinfo);
1140   n_cores = sysinfo.dwNumberOfProcessors;
1141
1142   return (size_t) n_cores;
1143 #else
1144 # warning "can not determine count of processor's cores."
1145   return 1;
1146 #endif
1147 }
1148
1149 struct build_options
1150 {
1151   uniqstr file;
1152   uniqstr target;
1153   uniqstr directory;
1154   size_t n_jobs;
1155   bool rebuild:1;
1156   bool dryrun:1;
1157   bool graph:1;
1158   bool verbose:1;
1159   bool list_targets:1;
1160 };
1161 static const char getopt_options[] = "f:j:t:d:Dgrvl";
1162 /*TODO
1163 static const options_t getopt_options =
1164   {
1165     ['f'] = { .is_option = true, .takes_argument = true },
1166     ['j'] = { .is_option = true, .takes_argument = true },
1167     ['t'] = { .is_option = true, .takes_argument = true },
1168     ['d'] = { .is_option = true, .takes_argument = true },
1169
1170     ['D'] = { .is_option = true, .takes_argument = false },
1171     ['g'] = { .is_option = true, .takes_argument = false },
1172     ['r'] = { .is_option = true, .takes_argument = false },
1173     ['v'] = { .is_option = true, .takes_argument = false },
1174     ['l'] = { .is_option = true, .takes_argument = false },
1175   };
1176 */
1177 static inline void
1178 build_options_initialize (struct build_options *o)
1179 {
1180   o->file = uniqstr_new_from_literal_string ("default.build");
1181   o->target = uniqstr_new_from_literal_string ("default");
1182   o->directory = NULL;
1183   o->n_jobs = 2 * get_count_of_processor_cores ();
1184   o->rebuild = false;
1185   o->dryrun = false;
1186   o->graph = false;
1187   o->verbose = false;
1188   o->list_targets = false;
1189 }
1190
1191 static inline bool ACCESS (write_only, 1) ACCESS (read_only, 2)
1192 string_to_number (size_t *number, const char *string)
1193 {
1194   size_t x = 0;
1195   const char *s = string;
1196
1197   while (((unsigned int) *s - '0') <= 9)
1198     {
1199       if (x > SIZE_MAX / 10 || (x * 10 > SIZE_MAX - (size_t) (*s - '0')))
1200         fatal (_("number is too big: %s"), string);
1201
1202       x = x * 10 + (size_t) (*s++ - '0');
1203     }
1204
1205   if (*s != '\0')
1206     {
1207       error ("unexpected character '%c' in number", *s);
1208       return false;
1209     }
1210
1211   *number = x;
1212   return true;
1213 }
1214
1215 static inline NODISCARD bool
1216 parse_options (struct build_options *o, int argc, char **argv)
1217 {
1218   int optc = -1;
1219
1220   while ((optc = getopt (argc, argv, getopt_options)) >= 0)
1221     {
1222       switch (optc)
1223         {
1224         case 'f':
1225           o->file = uniqstr_new (optarg);
1226           break;
1227         case 't':
1228           o->target = uniqstr_new (optarg);
1229           break;
1230         case 'd':
1231           o->directory = uniqstr_new (optarg);
1232           break;
1233         case 'j':
1234           if (!string_to_number (&o->n_jobs, optarg))
1235             return false;
1236
1237           break;
1238         case 'r':
1239           o->rebuild = true;
1240           break;
1241         case 'D':
1242           o->dryrun = true;
1243           break;
1244         case 'g':
1245           o->graph = true;
1246           break;
1247         case 'v':
1248           o->verbose = true;
1249           break;
1250         case 'l':
1251           o->list_targets = true;
1252           break;
1253         default:
1254           return false;
1255         }
1256     }
1257
1258   return true;
1259 }
1260
1261 static bool
1262 parse_build_file (uniqstr file,
1263                   struct build_context *context,
1264                   struct quoting_slots *qs)
1265 {
1266   yyscan_t yyscanner;
1267   YYLTYPE yylocation;
1268   int status;
1269   FILE *fp;
1270   YYETYPE extra;
1271
1272   if (UNLIKELY (yylex_init (&yyscanner) != 0))
1273     {
1274       error (_("failed to initialize flex scanner"));
1275       return false;
1276     }
1277
1278   fp = fopen (file, "r");
1279
1280   if (UNLIKELY (fp == NULL))
1281     {
1282       error (_("%s: can not open file: %s"),
1283              quotef (qs, file), strerror (errno));
1284       return false;
1285     }
1286
1287   extra.yylocation = &yylocation;
1288   extra.qs = qs;
1289   yylocation_initialize (&yylocation, uniqstr_new (quotef (qs, file)));
1290   yyset_extra (&extra, yyscanner);
1291   yyset_in (fp, yyscanner);
1292   yyset_out (stdout, yyscanner);
1293   status = yyparse (yyscanner, context);
1294   yylex_destroy (yyscanner);
1295   fclose (fp);
1296
1297   if (UNLIKELY (status != 0))
1298     {
1299       error (_("%s: parsing failed"), quotef (qs, file));
1300       return false;
1301     }
1302
1303   return true;
1304 }
1305
1306 static int
1307 uniqstr_comparator (uniqstr *u1, uniqstr *u2)
1308 {
1309   return uniqstr_cmp (*u1, *u2);
1310 }
1311
1312 static inline void
1313 target_list (const Hash *targets)
1314 {
1315   struct uniqstr_array array =
1316     {
1317       .count = targets->count,
1318       .array = xmallocarray (targets->count, sizeof (uniqstr))
1319     };
1320
1321   {
1322     HashElem *p = HashFirst (targets);
1323
1324     for (size_t i = 0; i < array.count; i++)
1325       {
1326         array.array[i] = ((struct target *) HashData (p))->name;
1327         p = HashNext (p);
1328       }
1329   }
1330
1331   qsort (array.array, array.count, sizeof (uniqstr),
1332          (int (*) (const void *, const void *)) uniqstr_comparator);
1333
1334   for (size_t i = 0; i < array.count; i++)
1335     puts (array.array[i]);
1336 }
1337
1338 int
1339 main (int argc, char **argv, char **envp)
1340 {
1341   struct build_context context;
1342   struct build_tree tree;
1343   struct quoting_slots quoting_slots;
1344   struct build_options options;
1345   struct watchdog watchdog;
1346   Hash table_for_loop_detection;
1347   Hash branches;
1348   Hash tracked_files;
1349
1350   setlocale (LC_ALL, "");
1351   diagnostic_initialize (argv[0]);
1352
1353   if (UNLIKELY (bindtextdomain (PACKAGE, LOCALEDIR) == NULL))
1354     warning (_("failed to set base directory for text domain"));
1355
1356   if (UNLIKELY (textdomain (PACKAGE) == NULL))
1357     warning (_("failed to set current message domain"));
1358
1359   quoting_slots_initialize (&quoting_slots);
1360   uniqstrs_table_create ();
1361   build_options_initialize (&options);
1362   context.default_target = NULL;
1363   HashInit (&context.skeletons);
1364   HashInit (&context.variables);
1365   HashInit (&context.rules);
1366   HashInit (&context.targets);
1367   //  HashInit (&context.depfiles);
1368   HashInit (&tracked_files);
1369
1370   if (UNLIKELY (!parse_options (&options, argc, argv)))
1371     return 1;
1372
1373   if (options.directory != NULL)
1374     if (chdir (options.directory) != 0)
1375       fatal (_("failed to change directory to %s: %s"),
1376              quotef (&quoting_slots, options.directory), strerror (errno));
1377
1378   if (options.verbose)
1379     diagnostic_enable_verbose ();
1380
1381   if (options.graph)
1382     {
1383       if (options.rebuild)
1384         warning (_("-r option is useless with -g option"));
1385
1386       if (options.dryrun)
1387         warning (_("-d option is useless with -g option"));
1388     }
1389
1390   if (UNLIKELY (!parse_build_file (options.file, &context, &quoting_slots)))
1391     return 1;
1392
1393   if (options.list_targets)
1394     {
1395       target_list (&context.targets);
1396       return 0;
1397     }
1398
1399   /*TODO  struct depfile_scanner depfile_scanner;
1400
1401   if (!depfile_scanner_initialize (&depfile_scanner, &quoting_slots))
1402     {
1403       error (_("failed to initialize dependency file scanner"));
1404       return 1;
1405     }
1406   */
1407
1408   if (UNLIKELY (!watchdog_initialize (&watchdog)))
1409     return 1;
1410
1411   /*TODO
1412   for (HashElem *p = HashFirst (&context.depfiles); p != NULL; p = HashNext (p))
1413     depfile_scan (&depfile_scanner, &watchdog, &tracked_files, HashData (p), &context.targets);
1414
1415   depfile_scanner_finalize (&depfile_scanner);
1416   */
1417   options.rebuild |= watchdog_track_file (&watchdog, &tracked_files, options.file, &quoting_slots);
1418   HashInit (&branches);
1419   HashInit (&table_for_loop_detection);
1420   tree.count_of_targets = 0;
1421
1422   uniqstr target = (options.target == NULL
1423                     ? (context.default_target == NULL
1424                        ? uniqstr_new_from_literal_string ("default")
1425                        : context.default_target)
1426                     : options.target);
1427
1428   if (UNLIKELY (!build_tree_create (&tree,
1429                                     &tree.root,
1430                                     &context.targets,
1431                                     &branches,
1432                                     options.rebuild,
1433                                     target,
1434                                     &watchdog,
1435                                     &quoting_slots,
1436                                     &table_for_loop_detection,
1437                                     &tracked_files)))
1438     {
1439       error (_("failed to create build-tree"));
1440       return 1;
1441     }
1442
1443   watchdog_finalize (&watchdog);
1444   //TODOtree.count_of_targets += (tree.root->target->skeleton->need_rebuild ? 1 : 0);
1445   HashClear (&table_for_loop_detection);
1446
1447   if (options.graph)
1448     graph (&tree);
1449   else if (UNLIKELY (!build_tree_traverse (&tree,
1450                                            &context.rules,
1451                                            envp,
1452                                            &tracked_files,
1453                                            options.dryrun,
1454                                            options.n_jobs)))
1455     {
1456       error (_("failed to build"));
1457       return 1;
1458     }
1459
1460   build_tree_destroy (&tree);
1461   HashClearWithDestructor (&tracked_files, free);
1462   HashClearWithDestructor (&branches, free);
1463   HashClearWithDestructor (&context.targets, free);
1464   HashClearWithDestructor (&context.rules, rule_destroy);
1465   HashClearWithDestructor (&context.variables, variable_destroy);
1466   HashClearWithDestructor (&context.skeletons, target_skeleton_destroy);
1467   uniqstrs_table_destroy ();
1468   quoting_slots_finalize (&quoting_slots);
1469   return 0;
1470 }