remake.cpp 79.6 KB
Newer Older
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1
/* -*- mode: C++; indent-tabs-mode: t; c-basic-offset: 8; -*- */
2 3 4 5 6 7 8 9
/**
@mainpage Remake, a build system that bridges the gap between make and redo.

As with <b>make</b>, <b>remake</b> uses a centralized rule file, which is
named <b>Remakefile</b>. It contains rules with a <em>make</em>-like
syntax:

@verbatim
Guillaume Melquiond's avatar
Guillaume Melquiond committed
10
target1 target2 ... : prerequisite1 prerequisite2 ...
11 12 13 14 15
	shell script
	that builds
	the targets
@endverbatim

Guillaume Melquiond's avatar
Guillaume Melquiond committed
16 17
A target is known to be up-to-date if all its prerequisites are. If it
has no known prerequisites yet the file already exits, it is assumed to
18 19 20 21 22
be up-to-date. Obsolete targets are rebuilt thanks to the shell script
provided by the rule.

As with <b>redo</b>, <b>remake</b> supports dynamic dependencies in
addition to these static dependencies. Whenever a script executes
Guillaume Melquiond's avatar
Guillaume Melquiond committed
23
`remake prerequisite4 prerequisite5 ...`, these prerequisites are
24
rebuilt if they are obsolete. (So <b>remake</b> acts like
Guillaume Melquiond's avatar
Guillaume Melquiond committed
25
<b>redo-ifchange</b>.) Moreover, all the dependencies are stored in file
26 27 28 29 30 31 32 33 34
<b>.remake</b> so that they are remembered in subsequent runs. Note that
dynamic dependencies from previous runs are only used to decide whether a
target is obsolete; they are not automatically rebuilt when they are
obsolete yet a target depends on them. They will only be rebuilt once the
dynamic call to <b>remake</b> is executed.

In other words, the following two rules have almost the same behavior.

@verbatim
Guillaume Melquiond's avatar
Guillaume Melquiond committed
35
target1 target2 ... : prerequisite1 prerequisite2 ...
36 37 38
	shell script

target1 target2 ... :
Guillaume Melquiond's avatar
Guillaume Melquiond committed
39
	remake prerequisite1 prerequisite2 ...
40 41 42 43
	shell script
@endverbatim

(There is a difference if the targets already exist, have never been
Guillaume Melquiond's avatar
Guillaume Melquiond committed
44
built before, and the prerequisites are either younger or obsolete, since
45 46 47 48 49 50 51
the targets will not be rebuilt in the second case.)

The above usage of dynamic dependencies is hardly useful. Their strength
lies in the fact that they can be computed on the fly:

@verbatim
%.o : %.c
Guillaume Melquiond's avatar
Guillaume Melquiond committed
52 53 54
	gcc -MMD -MF $@.d -o $@ -c $<
	remake -r < $@.d
	rm $@.d
55 56

%.cmo : %.ml
Guillaume Melquiond's avatar
Guillaume Melquiond committed
57 58
	ocamldep $< | remake -r $@
	ocamlc -c $<
59 60 61

after.xml: before.xml rules.xsl
	xsltproc --load-trace -o after.xml rules.xsl before.xml 2> deps
Guillaume Melquiond's avatar
Guillaume Melquiond committed
62
	remake `sed -n -e "\\,//,! s,^.*URL=\"\\([^\"]*\\).*\$,\\1,p" deps`
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
	rm deps
@endverbatim

Note that the first rule fails if any of the header files included by
a C source file has to be automatically generated. In that case, one
should perform a first call to <b>remake</b> them before calling the
compiler. (Dependencies from several calls to <b>remake</b> are
cumulative, so they will all be remembered the next time.)

\section sec-usage Usage

Usage: <tt>remake <i>options</i> <i>targets</i></tt>

Options:

Guillaume Melquiond's avatar
Guillaume Melquiond committed
78 79 80 81
- `-B`, `--always-make`: Unconditionally make all targets.
- `-d`: Echo script commands.
- `-f FILE`: Read `FILE` as <b>Remakefile</b>.
- `-j[N]`, `--jobs=[N]`: Allow `N` jobs at once;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
82
  infinite jobs with no argument.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
83 84 85
- `-k`, `--keep-going`: Keep going when some targets cannot be made.
- `-r`: Look up targets from the dependencies on standard input.
- `-s`, `--silent`, `--quiet`: Do not echo targets.
86 87 88 89 90 91

\section sec-syntax Syntax

Lines starting with a space character or a tabulation are assumed to be rule
scripts. They are only allowed after a rule header.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
92
Lines starting with `#` are considered to be comments and are ignored.
93 94
They do interrupt rule scripts though.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
95
Any other line is either a variable definition or a rule header. If such a
96 97 98
line ends with a backslash, the following line break is ignored and the line
extends to the next one.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
99 100 101
Variable definitions are a single name followed by equal followed by a list
of names, possibly empty.

102
Rule headers are a nonempty list of names, followed by a colon, followed by
Guillaume Melquiond's avatar
Guillaume Melquiond committed
103 104
another list of names, possibly empty. Basically, the syntax of a rule is as
follows:
105 106 107 108 109 110

@verbatim
targets : prerequisites
	shell script
@endverbatim

Guillaume Melquiond's avatar
Guillaume Melquiond committed
111 112 113
List of names are space-separated sequences of names. If a name contains
a space character, it should be put into double quotes. Names can not be
any of the following special characters `:$(),="`. Again, quotation
114 115 116 117 118
should be used. Quotation marks can be escaped by a backslash inside
quoted names.

\subsection sec-variables Variables

Guillaume Melquiond's avatar
Guillaume Melquiond committed
119
Variables can be used to factor lists of targets or prerequisites. They are
120 121 122
expanded as they are encountered during <b>Remakefile</b> parsing.

@verbatim
Guillaume Melquiond's avatar
Guillaume Melquiond committed
123
VAR2 = a
124
VAR1 = c d
Guillaume Melquiond's avatar
Guillaume Melquiond committed
125
VAR2 += $(VAR1) b
126 127 128
$(VAR2) e :
@endverbatim

Guillaume Melquiond's avatar
Guillaume Melquiond committed
129 130 131 132 133 134 135 136 137 138 139 140 141 142
Variable assignments can appear instead of prerequisites inside non-generic
rules with no script. They are then expanded inside the corresponding
generic rule.

@verbatim
foo.o: CFLAGS += -DBAR

%.o : %.c
	gcc $(CFLAGS) -MMD -MF $@.d -o $@ -c $<
	remake -r < $@.d
	rm $@.d
@endverbatim

Note: contrarily to <b>make</b>, variable names have to be enclosed in
Guillaume Melquiond's avatar
Guillaume Melquiond committed
143
parentheses. For instance, `$y` is not a shorthand for <tt>\$(y)</tt> and
Guillaume Melquiond's avatar
Guillaume Melquiond committed
144 145 146 147 148 149
is left unexpanded.

\subsection sec-autovars Automatic variables

The following special symbols can appear inside scripts:

Guillaume Melquiond's avatar
Guillaume Melquiond committed
150 151
- `$<` expands to the first static prerequisite of the rule.
- `$^` expands to all the static prerequisites of the rule, including
Guillaume Melquiond's avatar
Guillaume Melquiond committed
152
  duplicates if any.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
153 154 155
- `$@` expands to the first target of the rule.
- `$*` expands to the string that matched `%` in a generic rule.
- `$$` expands to a single dollar symbol.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
156

Guillaume Melquiond's avatar
Guillaume Melquiond committed
157 158 159 160
Note: contrarily to <b>make</b>, there are no corresponding variables.
For instance, `$^` is not a shorthand for `$(^)`. Another difference is
that `$@` is always the first target, not the one that triggered the
rule.
161 162 163 164 165 166 167 168 169 170

\subsection sec-functions Built-in functions

<b>remake</b> also supports a few built-in functions inspired from <b>make</b>.

- <tt>$(addprefix <i>prefix</i>, <i>list</i>)</tt> returns the list obtained
  by prepending its first argument to each element of its second argument.
- <tt>$(addsuffix <i>suffix</i>, <i>list</i>)</tt> returns the list obtained
  by appending its first argument to each element of its second argument.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
\subsection sec-order Order-only prerequisites

If the static prerequisites of a rule contain a pipe symbol, prerequisites
on its right do not cause the targets to become obsolete if they are newer
(unless they are also dynamically registered as dependencies). They are
meant to be used when the targets do not directly depend on them, but the
computation of their dynamic dependencies does.

@verbatim
%.o : %.c | parser.h
	gcc -MMD -MF $@.d -o $@ -c $<
	remake -r < $@.d
	rm $@.d

parser.c parser.h: parser.y
	yacc -d -o parser.c parser.y
@endverbatim

\subsection sec-special-tgt Special targets

Guillaume Melquiond's avatar
Guillaume Melquiond committed
191
Target `.PHONY` marks its prerequisites as being always obsolete.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
192 193 194

\subsection sec-special-var Special variables

Guillaume Melquiond's avatar
Guillaume Melquiond committed
195
Variable `.OPTIONS` is handled specially. Its content enables some
Guillaume Melquiond's avatar
Guillaume Melquiond committed
196 197
features of <b>remake</b> that are not enabled by default.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
198
- `variable-propagation`: When a variable is set in the prerequisite
Guillaume Melquiond's avatar
Guillaume Melquiond committed
199 200 201 202 203
  part of a rule, it is propagated to the rules of all the targets this rule
  depends on. This option also enables variables to be set on the command
  line. Note that, as in <b>make</b>, this features introduces non-determinism:
  the content of some variables will depend on the build order.

204 205 206 207 208 209 210 211
\section sec-semantics Semantics

\subsection src-obsolete When are targets obsolete?

A target is obsolete:

- if there is no file corresponding to the target, or to one of its siblings
  in a multi-target rule,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
212
- if any of its dynamic prerequisites from a previous run or any of its static
213 214
  prerequisites is obsolete,
- if the latest file corresponding to its siblings or itself is older than any
Guillaume Melquiond's avatar
Guillaume Melquiond committed
215
  of its dynamic prerequisites or static prerequisites.
216 217 218 219 220 221 222 223 224 225 226 227

In all the other cases, it is assumed to be up-to-date (and so are all its
siblings). Note that the last rule above says "latest" and not "earliest". While
it might cause some obsolete targets to go unnoticed in corner cases, it allows
for the following kind of rules:

@verbatim
config.h stamp-config_h: config.h.in config.status
	./config.status config.h
	touch stamp-config_h
@endverbatim

Guillaume Melquiond's avatar
Guillaume Melquiond committed
228 229 230 231 232 233
A `config.status` file generally does not update header files (here
`config.h`) if they would not change. As a consequence, if not for the
`stamp-config_h` file above, a header would always be considered obsolete
once one of its prerequisites is modified. Note that touching `config.h`
rather than `stamp-config_h` would defeat the point of not updating it in
the first place, since the program files would need to be rebuilt.
234 235

Once all the static prerequisites of a target have been rebuilt, <b>remake</b>
Guillaume Melquiond's avatar
Guillaume Melquiond committed
236 237 238
checks whether the target still needs to be built. If it was obsolete only
because its prerequisites needed to be rebuilt and none of them changed, the
target is assumed to be up-to-date.
239 240 241 242

\subsection sec-rules How are targets (re)built?

There are two kinds of rules. If any of the targets or prerequisites contains
Guillaume Melquiond's avatar
Guillaume Melquiond committed
243 244
a `%` character, the rule is said to be <em>generic</em>. All the
targets of the rule shall then contain a single `%` character. All the
245 246 247 248 249
other rules are said to be <em>specific</em>.

A rule is said to <em>match</em> a given target:

- if it is specific and the target appears inside its target list,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
250
- if it is generic and there is a way to replace the `%` character
251 252 253 254 255 256
  from one of its targets so that it matches the given target.

When <b>remake</b> tries to build a given target, it looks for a specific rule
that matches it. If there is one and its script is nonempty, it uses it to
rebuild the target.

Guillaume Melquiond's avatar
Guillaume Melquiond committed
257
Otherwise, it looks for a generic rule that matches the target. If there are
258
several matching rules, it chooses the one with the shortest pattern (and if
Guillaume Melquiond's avatar
Guillaume Melquiond committed
259 260 261 262
there are several ones, the earliest one). It then looks for specific rules
that match each target of the generic rule. All the prerequisites of these
specific rules are added to those of the generic rule. The script of the
generic rule is used to build the target.
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286

Example:

@verbatim
t%1 t2%: p1 p%2
	commands building t%1 and t2%

t2z: p4
	commands building t2z

ty1: p3

# t2x is built by the first rule (which also builds tx1) and its prerequisites are p1, px2
# t2y is built by the first rule (which also builds ty1) and its prerequisites are p1, py2, p3
# t2z is built by the second rule and its prerequisite is p4
@endverbatim

The set of rules from <b>Remakefile</b> is ill-formed:

- if any specific rule matching a target of the generic rule has a nonempty script,
- if any target of the generic rule is matched by a generic rule with a shorter pattern.

\section sec-compilation Compilation

Guillaume Melquiond's avatar
Guillaume Melquiond committed
287 288
- On Linux, MacOSX, and BSD: `g++ -o remake remake.cpp`
- On Windows: `g++ -o remake.exe remake.cpp -lws2_32`
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305

Installing <b>remake</b> is needed only if <b>Remakefile</b> does not
specify the path to the executable for its recursive calls. Thanks to its
single source file, <b>remake</b> can be shipped inside other packages and
built at configuration time.

\section sec-differences Differences with other build systems

Differences with <b>make</b>:

- Dynamic dependencies are supported.
- For rules with multiple targets, the shell script is executed only once
  and is assumed to build all the targets. There is no need for
  convoluted rules that are robust enough for parallel builds. For generic
  rules, this is similar to the behavior of pattern rules from <b>gmake</b>.
- As with <b>redo</b>, only one shell is run when executing a script,
  rather than one per script line. Note that the shells are run with
Guillaume Melquiond's avatar
Guillaume Melquiond committed
306
  option `-e`, thus causing them to exit as soon as an error is
307
  encountered.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
308 309 310
- The prerequisites of generic rules (known as implicit rules in <b>make</b>
  lingo) are not used to decide between several of them, which means that
  <b>remake</b> does not select one for which it could satisfy the dependencies.
311 312
- Variables and built-in functions are expanded as they are encountered
  during <b>Remakefile</b> parsing.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
313 314 315
- Target-specific variables are not propagated, unless specifically enabled,
  since this causes non-deterministic builds. This is the same for variables
  set on the command line.
316 317 318 319 320 321 322 323 324 325 326 327 328

Differences with <b>redo</b>:

- As with <b>make</b>, it is possible to write the following kind of rules
  in <b>remake</b>.
@verbatim
Remakefile: Remakefile.in ./config.status
	./config.status Remakefile
@endverbatim
- If a target is already built the first time <b>remake</b> runs, it still
  uses the static prerequisites of rules mentioning it to check whether it
  needs to be rebuilt. It does not assume it to be up-to-date. As with
  <b>redo</b> though, if its obsolete status would be due to a dynamic
Guillaume Melquiond's avatar
Guillaume Melquiond committed
329
  prerequisite, it will go unnoticed; it should be removed beforehand.
330
- Multiple targets are supported.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
331 332
- <b>remake</b> has almost no features: no checksum-based dependencies, no
  compatibility with job servers, etc.
333 334 335

\section sec-limitations Limitations

Guillaume Melquiond's avatar
Guillaume Melquiond committed
336 337
- If a rule script calls <b>remake</b>, the current working directory should
  be the directory containing <b>Remakefile</b> (or the working directory
Guillaume Melquiond's avatar
Guillaume Melquiond committed
338
  from the original <b>remake</b> if it was called with option `-f`).
Guillaume Melquiond's avatar
Guillaume Melquiond committed
339 340
- As with <b>make</b>, variables passed on the command line should keep
  the same values, to ensure deterministic builds.
341 342 343 344 345 346 347 348 349 350 351
- Some cases of ill-formed rules are not caught by <b>remake</b> and can
  thus lead to unpredictable behaviors.

\section sec-links Links

@see http://cr.yp.to/redo.html for the philosophy of <b>redo</b> and
https://github.com/apenwarr/redo for an implementation and some comprehensive documentation.

\section sec-licensing Licensing

@author Guillaume Melquiond
Guillaume Melquiond's avatar
Guillaume Melquiond committed
352 353
@version 0.13
@date 2012-2018
354 355 356 357 358 359 360 361 362 363
@copyright
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
\n
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381

\section sec-internals Internals

The parent <b>remake</b> process acts as a server. The other ones have a
REMAKE_SOCKET environment variable that tells them how to contact the
server. They send the content of the REMAKE_JOB_ID environment variable,
so that the server can associate the child targets to the jobs that
spawned them. They then wait for completion and exit with the status
returned by the server. This is handled by #client_mode.

The server calls #load_dependencies and #save_dependencies to serialize
dynamic dependencies from <b>.remake</b>. It loads <b>Remakefile</b> with
#load_rules. It then runs #server_mode, which calls #server_loop.

When building a target, the following sequence of events happens:

- #start calls #find_rule (and #find_generic_rule) to get the rule.
- It then creates a pseudo-client if the rule has static dependencies, or
Guillaume Melquiond's avatar
Guillaume Melquiond committed
382 383
  calls #run_script otherwise. In both cases, a new job is created; the
  rule and the variables are stored into #jobs.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
- #run_script creates a shell process and stores it in #job_pids. It
  increases #running_jobs.
- The child process possibly calls <b>remake</b> with a list of targets.
- #accept_client receives a build request from a child process and adds
  it to #clients. It also records the new dependencies of the job into
  #dependencies. It increases #waiting_jobs.
- #handle_clients uses #get_status to look up the obsoleteness of the
  targets.
- Once the targets of a request have been built or one of them has failed,
  #handle_clients calls #complete_request and removes the request from
  #clients.
- If the build targets come from a pseudo-client, #complete_request calls
  #run_script. Otherwise it sends the reply to the corresponding child
  process and decreases #waiting_jobs.
- When a child process ends, #server_loop calls #finalize_job, which
  removes the process from #job_pids, decreases #running_jobs, and calls
  #complete_job.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
401
- #complete_job removes the job from #jobs and calls #update_status
Guillaume Melquiond's avatar
Guillaume Melquiond committed
402 403
  to change the status of the targets. It also removes the target files in
  case of failure.
404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
*/

#ifdef _WIN32
#define WIN32_LEAN_AND_MEAN
#define WINDOWS
#endif

#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
Guillaume Melquiond's avatar
Guillaume Melquiond committed
421
#include <cstring>
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
#include <ctime>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>

#ifdef __APPLE__
#define MACOSX
#endif

#ifdef __linux__
#define LINUX
#endif

#ifdef WINDOWS
#include <windows.h>
#include <winbase.h>
#include <winsock2.h>
#define pid_t HANDLE
typedef SOCKET socket_t;
#else
#include <sys/socket.h>
#include <sys/un.h>
#include <sys/wait.h>
typedef int socket_t;
enum { INVALID_SOCKET = -1 };
Guillaume Melquiond's avatar
Guillaume Melquiond committed
450
extern char **environ;
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
#endif

#if defined(WINDOWS) || defined(MACOSX)
enum { MSG_NOSIGNAL = 0 };
#endif

typedef std::list<std::string> string_list;

typedef std::set<std::string> string_set;

/**
 * Reference-counted shared object.
 * @note The default constructor delays the creation of the object until it
 *       is first dereferenced.
 */
template<class T>
struct ref_ptr
{
	struct content
	{
		size_t cnt;
		T val;
		content(): cnt(1) {}
		content(T const &t): cnt(1), val(t) {}
	};
	mutable content *ptr;
	ref_ptr(): ptr(NULL) {}
	ref_ptr(T const &t): ptr(new content(t)) {}
	ref_ptr(ref_ptr const &p): ptr(p.ptr) { if (ptr) ++ptr->cnt; }
	~ref_ptr() { if (ptr && --ptr->cnt == 0) delete ptr; }
	ref_ptr &operator=(ref_ptr const &p)
	{
		if (ptr == p.ptr) return *this;
		if (ptr && --ptr->cnt == 0) delete ptr;
		ptr = p.ptr;
		if (ptr) ++ptr->cnt;
		return *this;
	}
	T &operator*() const
	{
		if (!ptr) ptr = new content;
		return ptr->val;
	}
	T *operator->() const { return &**this; }
};

struct dependency_t
{
	string_list targets;
	string_set deps;
};

typedef std::map<std::string, ref_ptr<dependency_t> > dependency_map;

typedef std::map<std::string, string_list> variable_map;

/**
 * Build status of a target.
 */
enum status_e
{
	Uptodate, ///< Target is up-to-date.
	Todo,     ///< Target is missing or obsolete.
	Recheck,  ///< Target has an obsolete dependency.
	Running,  ///< Target is being rebuilt.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
516
	RunningRecheck, ///< Static prerequisites are being rebuilt.
517 518 519 520 521 522 523 524 525 526 527 528 529 530 531
	Remade,   ///< Target was successfully rebuilt.
	Failed    ///< Build failed for target.
};

/**
 * Build status of a target.
 */
struct status_t
{
	status_e status; ///< Actual status.
	time_t last;     ///< Last-modified date.
};

typedef std::map<std::string, status_t> status_map;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
532 533 534 535 536 537 538 539 540
/**
 * Delayed assignment to a variable.
 */
struct assign_t
{
	bool append;
	string_list value;
};

Guillaume Melquiond's avatar
Guillaume Melquiond committed
541
typedef std::map<std::string, assign_t> assign_map;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
542

543 544 545 546 547 548
/**
 * A rule loaded from Remakefile.
 */
struct rule_t
{
	string_list targets; ///< Files produced by this rule.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
549 550 551
	string_list deps;    ///< Dependencies used for an implicit call to remake at the start of the script.
	string_list wdeps;   ///< Like #deps, except that they are not registered as dependencies.
	assign_map assigns;  ///< Assignment of variables.
552 553 554 555 556 557 558
	std::string script;  ///< Shell script for building the targets.
};

typedef std::list<rule_t> rule_list;

typedef std::map<std::string, ref_ptr<rule_t> > rule_map;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
559 560 561 562 563 564 565 566 567 568 569 570
/**
 * A job created from a set of rules.
 */

struct job_t
{
	rule_t rule;       ///< Original rule.
	std::string stem;  ///< Pattern used to instantiate the generic rule, if any.
	variable_map vars; ///< Values of local variables.
};

typedef std::map<int, job_t> job_map;
571 572 573 574

typedef std::map<pid_t, int> pid_job_map;

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
575
 * Client waiting for a request to complete.
576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
 *
 * There are two kinds of clients:
 * - real clients, which are instances of remake created by built scripts,
 * - pseudo clients, which are created by the server to build specific targets.
 *
 * Among pseudo clients, there are two categories:
 * - original clients, which are created for the targets passed on the
 *   command line by the user or for the initial regeneration of the rule file,
 * - dependency clients, which are created to handle rules that have
 *   explicit dependencies and thus to emulate a call to remake.
 */
struct client_t
{
	socket_t socket;     ///< Socket used to reply to the client (invalid for pseudo clients).
	int job_id;          ///< Job for which the built script called remake and spawned the client (negative for original clients).
	bool failed;         ///< Whether some targets failed in mode -k.
	string_list pending; ///< Targets not yet started.
	string_set running;  ///< Targets being built.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
594 595 596
	variable_map vars;   ///< Variables set on request.
	bool delayed;        ///< Whether it is a dependency client and a script has to be started on request completion.
	client_t(): socket(INVALID_SOCKET), job_id(-1), failed(false), delayed(false) {}
597 598 599 600 601 602
};

typedef std::list<client_t> client_list;

/**
 * Map from variable names to their content.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
603
 * Initialized with the values passed on the command line.
604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
 */
static variable_map variables;

/**
 * Map from targets to their known dependencies.
 */
static dependency_map dependencies;

/**
 * Map from targets to their build status.
 */
static status_map status;

/**
 * Set of generic rules loaded from Remakefile.
 */
static rule_list generic_rules;

/**
 * Map from targets to specific rules loaded from Remakefile.
 */
static rule_map specific_rules;

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
628
 * Map of jobs being built.
629
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
630
static job_map jobs;
631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677

/**
 * Map from jobs to shell pids.
 */
static pid_job_map job_pids;

/**
 * List of clients waiting for a request to complete.
 * New clients are put to front, so that the build process is depth-first.
 */
static client_list clients;

/**
 * Maximum number of parallel jobs (non-positive if unbounded).
 * Can be modified by the -j option.
 */
static int max_active_jobs = 1;

/**
 * Whether to keep building targets in case of failure.
 * Can be modified by the -k option.
 */
static bool keep_going = false;

/**
 * Number of jobs currently running:
 * - it increases when a process is created in #run_script,
 * - it decreases when a completion message is received in #finalize_job.
 *
 * @note There might be some jobs running while #clients is empty.
 *       Indeed, if a client requested two targets to be rebuilt, if they
 *       are running concurrently, if one of them fails, the client will
 *       get a failure notice and might terminate before the other target
 *       finishes.
 */
static int running_jobs = 0;

/**
 * Number of jobs currently waiting for a build request to finish:
 * - it increases when a build request is received in #accept_client
 *   (since the client is presumably waiting for the reply),
 * - it decreases when a reply is sent in #complete_request.
 */
static int waiting_jobs = 0;

/**
 * Global counter used to produce increasing job numbers.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
678
 * @see jobs
679 680 681 682 683 684 685 686 687 688 689 690 691
 */
static int job_counter = 0;

/**
 * Socket on which the server listens for client request.
 */
static socket_t socket_fd;

/**
 * Whether the request of an original client failed.
 */
static bool build_failure;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
692
#ifndef WINDOWS
693 694 695 696
/**
 * Name of the server socket in the file system.
 */
static char *socket_name;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
697
#endif
698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713

/**
 * Name of the first target of the first specific rule, used for default run.
 */
static std::string first_target;

/**
 * Whether a short message should be displayed for each target.
 */
static bool show_targets = true;

/**
 * Whether script commands are echoed.
 */
static bool echo_scripts = false;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
714 715 716
/**
 * Time at the start of the program.
 */
717 718
static time_t now = time(NULL);

Guillaume Melquiond's avatar
Guillaume Melquiond committed
719 720 721
/**
 * Directory with respect to which command-line names are relative.
 */
722 723
static std::string working_dir;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
724 725 726 727 728 729 730 731 732 733 734 735 736 737 738
/**
 * Directory with respect to which targets are relative.
 */
static std::string prefix_dir;

/**
 * Whether the prefix directory is different from #working_dir.
 */
static bool changed_prefix_dir;

/**
 * Whether target-specific variables are propagated to prerequisites.
 */
static bool propagate_vars = false;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
739 740 741 742 743
/**
 * Whether targets are unconditionally obsolete.
 */
static bool obsolete_targets = false;

744
#ifndef WINDOWS
Guillaume Melquiond's avatar
Guillaume Melquiond committed
745 746
static sigset_t old_sigmask;

747 748
static volatile sig_atomic_t got_SIGCHLD = 0;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
749
static void sigchld_handler(int)
750 751 752
{
	got_SIGCHLD = 1;
}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
753 754 755 756 757 758 759

static void sigint_handler(int)
{
	// Child processes will receive the signal too, so just prevent
	// new jobs from starting and wait for the running jobs to fail.
	keep_going = false;
}
760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788
#endif

struct log
{
	bool active, open;
	int depth;
	log(): active(false), open(false), depth(0)
	{
	}
	std::ostream &operator()()
	{
		if (open) std::cerr << std::endl;
		assert(depth >= 0);
		std::cerr << std::string(depth * 2, ' ');
		open = false;
		return std::cerr;
	}
	std::ostream &operator()(bool o)
	{
		if (o && open) std::cerr << std::endl;
		if (!o) --depth;
		assert(depth >= 0);
		if (o || !open) std::cerr << std::string(depth * 2, ' ');
		if (o) ++depth;
		open = o;
		return std::cerr;
	}
};

Guillaume Melquiond's avatar
Guillaume Melquiond committed
789
static log debug;
790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807

struct log_auto_close
{
	bool still_open;
	log_auto_close(): still_open(true)
	{
	}
	~log_auto_close()
	{
		if (debug.active && still_open) debug(false) << "done\n";
	}
};

#define DEBUG if (debug.active) debug()
#define DEBUG_open log_auto_close auto_close; if (debug.active) debug(true)
#define DEBUG_close if ((auto_close.still_open = false), debug.active) debug(false)

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
808 809 810 811 812 813 814 815 816 817 818 819 820
 * Strong typedef for strings that need escaping.
 * @note The string is stored as a reference, so the constructed object is
 *       meant to be immediately consumed.
 */
struct escape_string
{
	std::string const &input;
	escape_string(std::string const &s): input(s) {}
};

/**
 * Write the string in @a se to @a out if it does not contain any special
 * characters, a quoted and escaped string otherwise.
821
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
822
static std::ostream &operator<<(std::ostream &out, escape_string const &se)
823
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
824
	std::string const &s = se.input;
825 826 827
	char const *quoted_char = ",: '";
	char const *escaped_char = "\"\\$!";
	bool need_quotes = false;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
828 829
	char *buf = NULL;
	size_t len = s.length(), last = 0, j = 0;
830 831
	for (size_t i = 0; i < len; ++i)
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851
		if (strchr(escaped_char, s[i]))
		{
			need_quotes = true;
			if (!buf) buf = new char[len * 2];
			memcpy(&buf[j], &s[last], i - last);
			j += i - last;
			buf[j++] = '\\';
			buf[j++] = s[i];
			last = i + 1;
		}
		if (!need_quotes && strchr(quoted_char, s[i]))
			need_quotes = true;
	}
	if (!need_quotes) return out << s;
	out << '"';
	if (!buf) return out << s << '"';
	out.write(buf, j);
	out.write(&s[last], len - last);
	delete[] buf;
	return out << '"';
852 853
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
854 855 856 857 858 859
/**
 * @defgroup paths Path helpers
 *
 * @{
 */

860 861 862
/**
 * Initialize #working_dir.
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
863
static void init_working_dir()
864 865 866 867 868 869 870 871 872
{
	char buf[1024];
	char *res = getcwd(buf, sizeof(buf));
	if (!res)
	{
		perror("Failed to get working directory");
		exit(EXIT_FAILURE);
	}
	working_dir = buf;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
873 874 875 876 877 878 879
#ifdef WINDOWS
	for (size_t i = 0, l = working_dir.size(); i != l; ++i)
	{
		if (working_dir[i] == '\\') working_dir[i] = '/';
	}
#endif
	prefix_dir = working_dir;
880 881 882
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
883
 * Initialize #prefix_dir and switch to it.
884
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
885
static void init_prefix_dir()
886
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922
	for (;;)
	{
		struct stat s;
		if (stat((prefix_dir + "/Remakefile").c_str(), &s) == 0)
		{
			if (!changed_prefix_dir) return;
			if (chdir(prefix_dir.c_str()))
			{
				perror("Failed to change working directory");
				exit(EXIT_FAILURE);
			}
			if (show_targets)
			{
				std::cout << "remake: Entering directory `" << prefix_dir << '\'' << std::endl;
			}
			return;
		}
		size_t pos = prefix_dir.find_last_of('/');
		if (pos == std::string::npos)
		{
			std::cerr << "Failed to locate Remakefile in the current directory or one of its parents" << std::endl;
			exit(EXIT_FAILURE);
		}
		prefix_dir.erase(pos);
		changed_prefix_dir = true;
	}
}

/**
 * Normalize an absolute path with respect to @a p.
 * Paths outside the subtree are left unchanged.
 */
static std::string normalize_abs(std::string const &s, std::string const &p)
{
	size_t l = p.length();
	if (s.compare(0, l, p)) return s;
923 924 925 926 927 928 929 930 931 932 933 934 935
	size_t ll = s.length();
	if (ll == l) return ".";
	if (s[l] != '/')
	{
		size_t pos = s.rfind('/', l);
		assert(pos != std::string::npos);
		return s.substr(pos + 1);
	}
	if (ll == l + 1) return ".";
	return s.substr(l + 1);
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
936 937 938 939
 * Normalize path @a s (possibly relative to @a w) with respect to @a p.
 *
 * - If both @a p and @a w are empty, the function just removes ".", "..", "//".
 * - If only @a p is empty, the function returns an absolute path.
940
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
941
static std::string normalize(std::string const &s, std::string const &w, std::string const &p)
942 943 944 945 946 947 948
{
#ifdef WINDOWS
	char const *delim = "/\\";
#else
	char delim = '/';
#endif
	size_t pos = s.find_first_of(delim);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
949
	if (pos == std::string::npos && w == p) return s;
950
	bool absolute = pos == 0;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
951 952 953
	if (!absolute && w != p && !w.empty())
		return normalize(w + '/' + s, w, p);
	size_t prev = 0, len = s.length();
954 955 956 957 958 959 960 961 962
	string_list l;
	for (;;)
	{
		if (pos != prev)
		{
			std::string n = s.substr(prev, pos - prev);
			if (n == "..")
			{
				if (!l.empty()) l.pop_back();
Guillaume Melquiond's avatar
Guillaume Melquiond committed
963 964
				else if (!absolute && !w.empty())
					return normalize(w + '/' + s, w, p);
965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984
			}
			else if (n != ".")
				l.push_back(n);
		}
		++pos;
		if (pos >= len) break;
		prev = pos;
		pos = s.find_first_of(delim, prev);
		if (pos == std::string::npos) pos = len;
	}
	string_list::const_iterator i = l.begin(), i_end = l.end();
	if (i == i_end) return absolute ? "/" : ".";
	std::string n;
	if (absolute) n.push_back('/');
	n.append(*i);
	for (++i; i != i_end; ++i)
	{
		n.push_back('/');
		n.append(*i);
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
985
	if (absolute && !p.empty()) return normalize_abs(n, p);
986 987 988 989 990 991
	return n;
}

/**
 * Normalize the content of a list of targets.
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
992
static void normalize_list(string_list &l, std::string const &w, std::string const &p)
993 994 995 996
{
	for (string_list::iterator i = l.begin(),
	     i_end = l.end(); i != i_end; ++i)
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
997
		*i = normalize(*i, w, p);
998 999 1000
	}
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1001 1002 1003 1004 1005 1006 1007 1008
/** @} */

/**
 * @defgroup lexer Lexer
 *
 * @{
 */

1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
/**
 * Skip spaces.
 */
static void skip_spaces(std::istream &in)
{
	char c;
	while (strchr(" \t", (c = in.get()))) {}
	if (in.good()) in.putback(c);
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1020
 * Skip empty lines.
1021
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1022
static void skip_empty(std::istream &in)
1023 1024 1025 1026 1027 1028
{
	char c;
	while (strchr("\r\n", (c = in.get()))) {}
	if (in.good()) in.putback(c);
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
/**
 * Skip end of line. If @a multi is true, skip the following empty lines too.
 * @return true if there was a line to end.
 */
static bool skip_eol(std::istream &in, bool multi = false)
{
	char c = in.get();
	if (c == '\r') c = in.get();
	if (c != '\n' && in.good()) in.putback(c);
	if (c != '\n' && !in.eof()) return false;
	if (multi) skip_empty(in);
	return true;
}

enum
{
  Unexpected = 0,
  Word       = 1 << 1,
  Colon      = 1 << 2,
  Equal      = 1 << 3,
  Dollarpar  = 1 << 4,
  Rightpar   = 1 << 5,
  Comma      = 1 << 6,
  Plusequal  = 1 << 7,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1053
  Pipe       = 1 << 8,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1054
};
1055 1056

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1057 1058 1059 1060
 * Skip spaces and peek at the next token.
 * If it is one of @a mask, skip it (if it is not Word) and return it.
 * @note For composite tokens allowed by @a mask, input characters might
 *       have been eaten even for an Unexpected result.
1061
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1062
static int expect_token(std::istream &in, int mask)
1063 1064 1065 1066 1067
{
	while (true)
	{
		skip_spaces(in);
		char c = in.peek();
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1068 1069
		if (!in.good()) return Unexpected;
		int tok;
1070 1071 1072
		switch (c)
		{
		case '\r':
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1073 1074 1075 1076 1077
		case '\n': return Unexpected;
		case ':': tok = Colon; break;
		case ',': tok = Comma; break;
		case '=': tok = Equal; break;
		case ')': tok = Rightpar; break;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1078
		case '|': tok = Pipe; break;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1079 1080
		case '$':
			if (!(mask & Dollarpar)) return Unexpected;
1081
			in.ignore(1);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1082 1083 1084 1085 1086 1087 1088 1089
			tok = Dollarpar;
			if (in.peek() != '(') return Unexpected;
			break;
		case '+':
			if (!(mask & Plusequal)) return Unexpected;
			in.ignore(1);
			tok = Plusequal;
			if (in.peek() != '=') return Unexpected;
1090
			break;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1091 1092 1093 1094 1095
		case '\\':
			in.ignore(1);
			if (skip_eol(in)) continue;
			in.putback('\\');
			return mask & Word ? Word : Unexpected;
1096
		default:
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1097
			return mask & Word ? Word : Unexpected;
1098
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1099 1100 1101
		if (!(tok & mask)) return Unexpected;
		in.ignore(1);
		return tok;
1102 1103 1104 1105 1106 1107
	}
}

/**
 * Read a (possibly quoted) word.
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1108
static std::string read_word(std::istream &in, bool detect_equal = true)
1109
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1110
	int c = in.peek();
1111 1112
	std::string res;
	if (!in.good()) return res;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1113
	char const *separators = " \t\r\n$(),:";
1114
	bool quoted = c == '"';
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1115 1116
	if (quoted) in.ignore(1);
	bool plus = false;
1117 1118
	while (true)
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1119
		c = in.peek();
1120 1121 1122
		if (!in.good()) return res;
		if (quoted)
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1123
			in.ignore(1);
1124 1125 1126
			if (c == '\\')
				res += in.get();
			else if (c == '"')
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1127
				quoted = false;
1128 1129
			else
				res += c;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1130
			continue;
1131
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1132
		if (detect_equal && c == '=')
1133
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1134 1135 1136 1137 1138 1139 1140
			if (plus) in.putback('+');
			return res;
		}
		if (plus)
		{
			res += '+';
			plus = false;
1141
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1142 1143 1144 1145
		if (strchr(separators, c)) return res;
		in.ignore(1);
		if (detect_equal && c == '+') plus = true;
		else res += c;
1146 1147 1148
	}
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1149 1150 1151 1152 1153 1154 1155
/** @} */

/**
 * @defgroup stream Token streams
 *
 * @{
 */
1156 1157

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1158
 * Possible results from word producers.
1159
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1160
enum input_status
1161
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181
	Success,
	SyntaxError,
	Eof
};

/**
 * Interface for word producers.
 */
struct generator
{
	virtual ~generator() {}
	virtual input_status next(std::string &) = 0;
};

/**
 * Generator for the words of a variable.
 */
struct variable_generator: generator
{
	std::string name;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1182 1183
	string_list::const_iterator vcur, vend;
	variable_generator(std::string const &, variable_map const *);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1184 1185 1186 1187
	input_status next(std::string &);
};

variable_generator::variable_generator(std::string const &n,
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1188
	variable_map const *local_variables): name(n)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1189 1190
{
	if (local_variables)
1191
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1192 1193
		variable_map::const_iterator i = local_variables->find(name);
		if (i != local_variables->end())
1194
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1195 1196 1197
			vcur = i->second.begin();
			vend = i->second.end();
			return;
1198 1199
		}
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1200 1201 1202 1203
	variable_map::const_iterator i = variables.find(name);
	if (i == variables.end()) return;
	vcur = i->second.begin();
	vend = i->second.end();
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1204 1205 1206 1207
}

input_status variable_generator::next(std::string &res)
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1208
	if (vcur != vend)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1209
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1210 1211
		res = *vcur;
		++vcur;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1212 1213 1214
		return Success;
	}
	return Eof;
1215 1216 1217
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1218
 * Generator for the words of an input stream.
1219
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1220
struct input_generator
1221
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1222 1223
	std::istream &in;
	generator *nested;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1224
	variable_map const *local_variables;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1225
	bool earliest_exit, done;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1226
	input_generator(std::istream &i, variable_map const *lv, bool e = false)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249
		: in(i), nested(NULL), local_variables(lv), earliest_exit(e), done(false) {}
	input_status next(std::string &);
	~input_generator() { assert(!nested); }
};

static generator *get_function(input_generator const &, std::string const &);

input_status input_generator::next(std::string &res)
{
	if (nested)
	{
		restart:
		input_status s = nested->next(res);
		if (s == Success) return Success;
		delete nested;
		nested = NULL;
		if (s == SyntaxError) return SyntaxError;
	}
	if (done) return Eof;
	if (earliest_exit) done = true;
	switch (expect_token(in, Word | Dollarpar))
	{
	case Word:
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1250
		res = read_word(in, false);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1251 1252 1253
		return Success;
	case Dollarpar:
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1254
		std::string name = read_word(in, false);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1255 1256 1257 1258 1259 1260 1261 1262 1263
		if (name.empty()) return SyntaxError;
		if (expect_token(in, Rightpar))
			nested = new variable_generator(name, local_variables);
		else
		{
			nested = get_function(*this, name);
			if (!nested) return SyntaxError;
		}
		goto restart;
1264
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275
	default:
		return Eof;
	}
}

/**
 * Read a list of words from an input generator.
 * @return false if a syntax error was encountered.
 */
static bool read_words(input_generator &in, string_list &res)
{
1276 1277
	while (true)
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321
		res.push_back(std::string());
		input_status s = in.next(res.back());
		if (s == Success) continue;
		res.pop_back();
		return s == Eof;
	}
}

static bool read_words(std::istream &in, string_list &res)
{
	input_generator gen(in, NULL);
	return read_words(gen, res);
}

/**
 * Generator for the result of function addprefix.
 */
struct addprefix_generator: generator
{
	input_generator gen;
	string_list pre;
	string_list::const_iterator prei;
	size_t prej, prel;
	std::string suf;
	addprefix_generator(input_generator const &, bool &);
	input_status next(std::string &);
};

addprefix_generator::addprefix_generator(input_generator const &top, bool &ok)
	: gen(top.in, top.local_variables)
{
	if (!read_words(gen, pre)) return;
	if (!expect_token(gen.in, Comma)) return;
	prej = 0;
	prel = pre.size();
	ok = true;
}

input_status addprefix_generator::next(std::string &res)
{
	if (prej)
	{
		produce:
		if (prej == prel)
1322
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1323 1324 1325 1326
			res = *prei + suf;
			prej = 0;
		}
		else
1327
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1328 1329
			res = *prei++;
			++prej;
1330
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380
		return Success;
	}
	switch (gen.next(res))
	{
	case Success:
		if (!prel) return Success;
		prei = pre.begin();
		prej = 1;
		suf = res;
		goto produce;
	case Eof:
		return expect_token(gen.in, Rightpar) ? Eof : SyntaxError;
	default:
		return SyntaxError;
	}
}

/**
 * Generator for the result of function addsuffix.
 */
struct addsuffix_generator: generator
{
	input_generator gen;
	string_list suf;
	string_list::const_iterator sufi;
	size_t sufj, sufl;
	std::string pre;
	addsuffix_generator(input_generator const &, bool &);
	input_status next(std::string &);
};

addsuffix_generator::addsuffix_generator(input_generator const &top, bool &ok)
	: gen(top.in, top.local_variables)
{
	if (!read_words(gen, suf)) return;
	if (!expect_token(gen.in, Comma)) return;
	sufj = 0;
	sufl = suf.size();
	ok = true;
}

input_status addsuffix_generator::next(std::string &res)
{
	if (sufj)
	{
		if (sufj != sufl)
		{
			res = *sufi++;
			++sufj;
			return Success;
1381
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395
		sufj = 0;
	}
	switch (gen.next(res))
	{
	case Success:
		if (!sufl) return Success;
		sufi = suf.begin();
		sufj = 1;
		res += *sufi++;
		return Success;
	case Eof:
		return expect_token(gen.in, Rightpar) ? Eof : SyntaxError;
	default:
		return SyntaxError;
1396 1397 1398
	}
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1399 1400 1401
/**
 * Return a generator for function @a name.
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1402
static generator *get_function(input_generator const &in, std::string const &name)
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421
{
	skip_spaces(in.in);
	generator *g = NULL;
	bool ok = false;
	if (name == "addprefix") g = new addprefix_generator(in, ok);
	else if (name == "addsuffix") g = new addsuffix_generator(in, ok);
	if (!g || ok) return g;
	delete g;
	return NULL;
}

/** @} */

/**
 * @defgroup database Dependency database
 *
 * @{
 */

1422 1423 1424 1425 1426
/**
 * Load dependencies from @a in.
 */
static void load_dependencies(std::istream &in)
{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1427 1428 1429 1430 1431 1432 1433
	if (false)
	{
		error:
		std::cerr << "Failed to load database" << std::endl;
		exit(EXIT_FAILURE);
	}

1434 1435
	while (!in.eof())
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1436 1437 1438 1439
		string_list targets;
		if (!read_words(in, targets)) goto error;
		if (in.eof()) return;
		if (targets.empty()) goto error;
1440
		DEBUG << "reading dependencies of target " << targets.front() << std::endl;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1441
		if (in.get() != ':') goto error;
1442 1443
		ref_ptr<dependency_t> dep;
		dep->targets = targets;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1444 1445 1446
		string_list deps;
		if (!read_words(in, deps)) goto error;
		dep->deps.insert(deps.begin(), deps.end());
1447 1448 1449 1450 1451
		for (string_list::const_iterator i = targets.begin(),
		     i_end = targets.end(); i != i_end; ++i)
		{
			dependencies[*i] = dep;
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1452
		skip_empty(in);
1453 1454 1455 1456
	}
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1457
 * Load known dependencies from file `.remake`.
1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470
 */
static void load_dependencies()
{
	DEBUG_open << "Loading database... ";
	std::ifstream in(".remake");
	if (!in.good())
	{
		DEBUG_close << "not found\n";
		return;
	}
	load_dependencies(in);
}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1471 1472

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1473
 * Save all the dependencies in file `.remake`.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499
 */
static void save_dependencies()
{
	DEBUG_open << "Saving database... ";
	std::ofstream db(".remake");
	while (!dependencies.empty())
	{
		ref_ptr<dependency_t> dep = dependencies.begin()->second;
		for (string_list::const_iterator i = dep->targets.begin(),
		     i_end = dep->targets.end(); i != i_end; ++i)
		{
			db << escape_string(*i) << ' ';
			dependencies.erase(*i);
		}
		db << ':';
		for (string_set::const_iterator i = dep->deps.begin(),
		     i_end = dep->deps.end(); i != i_end; ++i)
		{
			db << ' ' << escape_string(*i);
		}
		db << std::endl;
	}
}

/** @} */

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1500 1501
static void merge_rule(rule_t &dest, rule_t const &src);

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537
/**
 * @defgroup parser Rule parser
 *
 * @{
 */

/**
 * Register a specific rule with an empty script:
 *
 * - Check that none of the targets already has an associated rule with a
 *   nonempty script.
 * - Create a new rule with a single target for each target, if needed.
 * - Add the prerequisites of @a rule to all these associated rules.
 */
static void register_transparent_rule(rule_t const &rule, string_list const &targets)
{
	assert(rule.script.empty());
	for (string_list::const_iterator i = targets.begin(),
	     i_end = targets.end(); i != i_end; ++i)
	{
		std::pair<rule_map::iterator, bool> j =
			specific_rules.insert(std::make_pair(*i, ref_ptr<rule_t>()));
		ref_ptr<rule_t> &r = j.first->second;
		if (j.second)
		{
			r = ref_ptr<rule_t>(rule);
			r->targets = string_list(1, *i);
			continue;
		}
		if (!r->script.empty())
		{
			std::cerr << "Failed to load rules: " << *i
				<< " cannot be the target of several rules" << std::endl;
			exit(EXIT_FAILURE);
		}
		assert(r->targets.size() == 1 && r->targets.front() == *i);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1538
		merge_rule(*r, rule);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584
	}

	for (string_list::const_iterator i = targets.begin(),
	     i_end = targets.end(); i != i_end; ++i)
	{
		ref_ptr<dependency_t> &dep = dependencies[*i];
		if (dep->targets.empty()) dep->targets.push_back(*i);
		dep->deps.insert(rule.deps.begin(), rule.deps.end());
	}
}

/**
 * Register a specific rule with a nonempty script:
 *
 * - Check that none of the targets already has an associated rule.
 * - Create a single shared rule and associate it to all the targets.
 * - Merge the prerequisites of all the targets into a single set and
 *   add the prerequisites of the rule to it. (The preexisting
 *   prerequisites, if any, come from a previous run.)
 */
static void register_scripted_rule(rule_t const &rule)
{
	ref_ptr<rule_t> r(rule);
	for (string_list::const_iterator i = rule.targets.begin(),
	     i_end = rule.targets.end(); i != i_end; ++i)
	{
		std::pair<rule_map::iterator, bool> j =
			specific_rules.insert(std::make_pair(*i, r));
		if (j.second) continue;
		std::cerr << "Failed to load rules: " << *i
			<< " cannot be the target of several rules" << std::endl;
		exit(EXIT_FAILURE);
	}

	ref_ptr<dependency_t> dep;
	dep->targets = rule.targets;
	dep->deps.insert(rule.deps.begin(), rule.deps.end());
	for (string_list::const_iterator i = rule.targets.begin(),
	     i_end = rule.targets.end(); i != i_end; ++i)
	{
		ref_ptr<dependency_t> &d = dependencies[*i];
		dep->deps.insert(d->deps.begin(), d->deps.end());
		d = dep;
	}
}

1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601
/**
 * Read a rule starting with target @a first, if nonempty.
 * Store into #generic_rules or #specific_rules depending on its genericity.
 */
static void load_rule(std::istream &in, std::string const &first)
{
	DEBUG_open << "Reading rule for target " << first << "... ";
	if (false)
	{
		error:
		DEBUG_close << "failed\n";
		std::cerr << "Failed to load rules: syntax error" << std::endl;
		exit(EXIT_FAILURE);
	}
	rule_t rule;

	// Read targets and check genericity.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1602 1603
	string_list targets;
	if (!read_words(in, targets)) goto error;
1604 1605 1606 1607
	if (!first.empty()) targets.push_front(first);
	else if (targets.empty()) goto error;
	else DEBUG << "actual target: " << targets.front() << std::endl;
	bool generic = false;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1608
	normalize_list(targets, "", "");
1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622
	for (string_list::const_iterator i = targets.begin(),
	     i_end = targets.end(); i != i_end; ++i)
	{
		if (i->empty()) goto error;
		if ((i->find('%') != std::string::npos) != generic)
		{
			if (i == targets.begin()) generic = true;
			else goto error;
		}
	}
	std::swap(rule.targets, targets);
	skip_spaces(in);
	if (in.get() != ':') goto error;

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1623 1624
	bool assignment = false;

1625
	// Read dependencies.
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1626
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1627 1628
		string_list v;
		if (expect_token(in, Word))
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1629
		{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640
			std::string d = read_word(in);
			if (int tok = expect_token(in, Equal | Plusequal))
			{
				if (!read_words(in, v)) goto error;
				assign_t &a = rule.assigns[d];
				a.append = tok == Plusequal;
				a.value.swap(v);
				assignment = true;
				goto end_line;
			}
			v.push_back(d);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1641
		}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1642 1643 1644 1645 1646 1647

		if (!read_words(in, v)) goto error;
		normalize_list(v, "", "");
		rule.deps.swap(v);

		if (expect_token(in, Pipe))
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1648 1649
		{
			if (!read_words(in, v)) goto error;
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1650 1651
			normalize_list(v, "", "");
			rule.wdeps.swap(v);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1652 1653
		}
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1654 1655

	end_line:
1656
	skip_spaces(in);
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1657
	if (!skip_eol(in, true)) goto error;
1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679

	// Read script.
	std::ostringstream buf;
	while (true)
	{
		char c = in.get();
		if (!in.good()) break;
		if (c == '\t' || c == ' ')
		{
			in.get(*buf.rdbuf());
			if (in.fail() && !in.eof()) in.clear();
		}
		else if (c == '\r' || c == '\n')
			buf << c;
		else
		{
			in.putback(c);
			break;
		}
	}
	rule.script = buf.str();

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690
	// Register phony targets.
	if (rule.targets.front() == ".PHONY")
	{
		for (string_list::const_iterator i = rule.deps.begin(),
		     i_end = rule.deps.end(); i != i_end; ++i)
		{
			status[*i].status = Todo;
		}
		return;
	}

1691 1692 1693
	// Add generic rules to the correct set.
	if (generic)
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1694
		if (assignment) goto error;
1695 1696 1697 1698 1699 1700
		generic_rules.push_back(rule);
		return;
	}

	if (!rule.script.empty())
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1701 1702
		if (assignment) goto error;
		register_scripted_rule(rule);
1703 1704 1705
	}
	else
	{
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1706 1707 1708 1709 1710
		// Swap away the targets to avoid costly copies when registering.
		string_list targets;
		std::swap(rule.targets, targets);
		register_transparent_rule(rule, targets);
		std::swap(rule.targets, targets);
1711 1712
	}

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1713
	// If there is no default target yet, mark it as such.
1714 1715 1716 1717 1718
	if (first_target.empty())
		first_target = rule.targets.front();
}

/**
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1719
 * Load rules from @a remakefile.
1720 1721 1722
 * If some rules have dependencies and non-generic targets, add these
 * dependencies to the targets.
 */
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1723
static void load_rules(std::string const &remakefile)
1724 1725 1726 1727 1728 1729 1730 1731
{
	DEBUG_open << "Loading rules... ";
	if (false)
	{
		error:
		std::cerr << "Failed to load rules: syntax error" << std::endl;
		exit(EXIT_FAILURE);
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1732
	std::ifstream in(remakefile.c_str());
1733 1734 1735 1736 1737
	if (!in.good())
	{
		std::cerr << "Failed to load rules: no Remakefile found" << std::endl;
		exit(EXIT_FAILURE);
	}
Guillaume Melquiond's avatar
Guillaume Melquiond committed
1738
	skip_empty(in);
1739

Guillaume Melquiond's avatar
Guillaume Melquiond committed
1740 1741
	string_list options;

1742 1743 1744 1745 1746 1747 1748
	// Read rules
	while (in.good())
	{
		char c = in.peek();
		if (c == '#')
		{
			while (in.get() != '\n') {}