Ninja
util.cc
Go to the documentation of this file.
1 // Copyright 2011 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include "util.h"
16 
17 #ifdef __CYGWIN__
18 #include <windows.h>
19 #include <io.h>
20 #elif defined( _WIN32)
21 #include <windows.h>
22 #include <io.h>
23 #include <share.h>
24 #endif
25 
26 #include <assert.h>
27 #include <errno.h>
28 #include <fcntl.h>
29 #include <stdarg.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <sys/stat.h>
34 #include <sys/types.h>
35 
36 #ifndef _WIN32
37 #include <unistd.h>
38 #include <sys/time.h>
39 #endif
40 
41 #include <vector>
42 
43 #if defined(__APPLE__) || defined(__FreeBSD__)
44 #include <sys/sysctl.h>
45 #elif defined(__SVR4) && defined(__sun)
46 #include <unistd.h>
47 #include <sys/loadavg.h>
48 #elif defined(linux) || defined(__GLIBC__)
49 #include <sys/sysinfo.h>
50 #endif
51 
52 #include "edit_distance.h"
53 #include "metrics.h"
54 
55 void Fatal(const char* msg, ...) {
56  va_list ap;
57  fprintf(stderr, "ninja: fatal: ");
58  va_start(ap, msg);
59  vfprintf(stderr, msg, ap);
60  va_end(ap);
61  fprintf(stderr, "\n");
62 #ifdef _WIN32
63  // On Windows, some tools may inject extra threads.
64  // exit() may block on locks held by those threads, so forcibly exit.
65  fflush(stderr);
66  fflush(stdout);
67  ExitProcess(1);
68 #else
69  exit(1);
70 #endif
71 }
72 
73 void Warning(const char* msg, ...) {
74  va_list ap;
75  fprintf(stderr, "ninja: warning: ");
76  va_start(ap, msg);
77  vfprintf(stderr, msg, ap);
78  va_end(ap);
79  fprintf(stderr, "\n");
80 }
81 
82 void Error(const char* msg, ...) {
83  va_list ap;
84  fprintf(stderr, "ninja: error: ");
85  va_start(ap, msg);
86  vfprintf(stderr, msg, ap);
87  va_end(ap);
88  fprintf(stderr, "\n");
89 }
90 
91 bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err) {
92  METRIC_RECORD("canonicalize str");
93  size_t len = path->size();
94  char* str = 0;
95  if (len > 0)
96  str = &(*path)[0];
97  if (!CanonicalizePath(str, &len, slash_bits, err))
98  return false;
99  path->resize(len);
100  return true;
101 }
102 
103 #ifdef _WIN32
104 static unsigned int ShiftOverBit(int offset, unsigned int bits) {
105  // e.g. for |offset| == 2:
106  // | ... 9 8 7 6 5 4 3 2 1 0 |
107  // \_________________/ \_/
108  // above below
109  // So we drop the bit at offset and move above "down" into its place.
110  unsigned int above = bits & ~((1 << (offset + 1)) - 1);
111  unsigned int below = bits & ((1 << offset) - 1);
112  return (above >> 1) | below;
113 }
114 #endif
115 
116 bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits,
117  string* err) {
118  // WARNING: this function is performance-critical; please benchmark
119  // any changes you make to it.
120  METRIC_RECORD("canonicalize path");
121  if (*len == 0) {
122  *err = "empty path";
123  return false;
124  }
125 
126  const int kMaxPathComponents = 30;
127  char* components[kMaxPathComponents];
128  int component_count = 0;
129 
130  char* start = path;
131  char* dst = start;
132  const char* src = start;
133  const char* end = start + *len;
134 
135 #ifdef _WIN32
136  unsigned int bits = 0;
137  unsigned int bits_mask = 1;
138  int bits_offset = 0;
139  // Convert \ to /, setting a bit in |bits| for each \ encountered.
140  for (char* c = path; c < end; ++c) {
141  switch (*c) {
142  case '\\':
143  bits |= bits_mask;
144  *c = '/';
145  // Intentional fallthrough.
146  case '/':
147  bits_mask <<= 1;
148  bits_offset++;
149  }
150  }
151  if (bits_offset > 32) {
152  *err = "too many path components";
153  return false;
154  }
155  bits_offset = 0;
156 #endif
157 
158  if (*src == '/') {
159 #ifdef _WIN32
160  bits_offset++;
161  // network path starts with //
162  if (*len > 1 && *(src + 1) == '/') {
163  src += 2;
164  dst += 2;
165  bits_offset++;
166  } else {
167  ++src;
168  ++dst;
169  }
170 #else
171  ++src;
172  ++dst;
173 #endif
174  }
175 
176  while (src < end) {
177  if (*src == '.') {
178  if (src + 1 == end || src[1] == '/') {
179  // '.' component; eliminate.
180  src += 2;
181 #ifdef _WIN32
182  bits = ShiftOverBit(bits_offset, bits);
183 #endif
184  continue;
185  } else if (src[1] == '.' && (src + 2 == end || src[2] == '/')) {
186  // '..' component. Back up if possible.
187  if (component_count > 0) {
188  dst = components[component_count - 1];
189  src += 3;
190  --component_count;
191 #ifdef _WIN32
192  bits = ShiftOverBit(bits_offset, bits);
193  bits_offset--;
194  bits = ShiftOverBit(bits_offset, bits);
195 #endif
196  } else {
197  *dst++ = *src++;
198  *dst++ = *src++;
199  *dst++ = *src++;
200  }
201  continue;
202  }
203  }
204 
205  if (*src == '/') {
206  src++;
207 #ifdef _WIN32
208  bits = ShiftOverBit(bits_offset, bits);
209 #endif
210  continue;
211  }
212 
213  if (component_count == kMaxPathComponents)
214  Fatal("path has too many components : %s", path);
215  components[component_count] = dst;
216  ++component_count;
217 
218  while (*src != '/' && src != end)
219  *dst++ = *src++;
220 #ifdef _WIN32
221  bits_offset++;
222 #endif
223  *dst++ = *src++; // Copy '/' or final \0 character as well.
224  }
225 
226  if (dst == start) {
227  *err = "path canonicalizes to the empty path";
228  return false;
229  }
230 
231  *len = dst - start - 1;
232 #ifdef _WIN32
233  *slash_bits = bits;
234 #else
235  *slash_bits = 0;
236 #endif
237  return true;
238 }
239 
240 static inline bool IsKnownShellSafeCharacter(char ch) {
241  if ('A' <= ch && ch <= 'Z') return true;
242  if ('a' <= ch && ch <= 'z') return true;
243  if ('0' <= ch && ch <= '9') return true;
244 
245  switch (ch) {
246  case '_':
247  case '+':
248  case '-':
249  case '.':
250  case '/':
251  return true;
252  default:
253  return false;
254  }
255 }
256 
257 static inline bool IsKnownWin32SafeCharacter(char ch) {
258  switch (ch) {
259  case ' ':
260  case '"':
261  return false;
262  default:
263  return true;
264  }
265 }
266 
267 static inline bool StringNeedsShellEscaping(const string& input) {
268  for (size_t i = 0; i < input.size(); ++i) {
269  if (!IsKnownShellSafeCharacter(input[i])) return true;
270  }
271  return false;
272 }
273 
274 static inline bool StringNeedsWin32Escaping(const string& input) {
275  for (size_t i = 0; i < input.size(); ++i) {
276  if (!IsKnownWin32SafeCharacter(input[i])) return true;
277  }
278  return false;
279 }
280 
281 void GetShellEscapedString(const string& input, string* result) {
282  assert(result);
283 
284  if (!StringNeedsShellEscaping(input)) {
285  result->append(input);
286  return;
287  }
288 
289  const char kQuote = '\'';
290  const char kEscapeSequence[] = "'\\'";
291 
292  result->push_back(kQuote);
293 
294  string::const_iterator span_begin = input.begin();
295  for (string::const_iterator it = input.begin(), end = input.end(); it != end;
296  ++it) {
297  if (*it == kQuote) {
298  result->append(span_begin, it);
299  result->append(kEscapeSequence);
300  span_begin = it;
301  }
302  }
303  result->append(span_begin, input.end());
304  result->push_back(kQuote);
305 }
306 
307 
308 void GetWin32EscapedString(const string& input, string* result) {
309  assert(result);
310  if (!StringNeedsWin32Escaping(input)) {
311  result->append(input);
312  return;
313  }
314 
315  const char kQuote = '"';
316  const char kBackslash = '\\';
317 
318  result->push_back(kQuote);
319  size_t consecutive_backslash_count = 0;
320  string::const_iterator span_begin = input.begin();
321  for (string::const_iterator it = input.begin(), end = input.end(); it != end;
322  ++it) {
323  switch (*it) {
324  case kBackslash:
325  ++consecutive_backslash_count;
326  break;
327  case kQuote:
328  result->append(span_begin, it);
329  result->append(consecutive_backslash_count + 1, kBackslash);
330  span_begin = it;
331  consecutive_backslash_count = 0;
332  break;
333  default:
334  consecutive_backslash_count = 0;
335  break;
336  }
337  }
338  result->append(span_begin, input.end());
339  result->append(consecutive_backslash_count, kBackslash);
340  result->push_back(kQuote);
341 }
342 
343 int ReadFile(const string& path, string* contents, string* err) {
344 #ifdef _WIN32
345  // This makes a ninja run on a set of 1500 manifest files about 4% faster
346  // than using the generic fopen code below.
347  err->clear();
348  HANDLE f = ::CreateFile(path.c_str(),
349  GENERIC_READ,
350  FILE_SHARE_READ,
351  NULL,
352  OPEN_EXISTING,
353  FILE_FLAG_SEQUENTIAL_SCAN,
354  NULL);
355  if (f == INVALID_HANDLE_VALUE) {
356  err->assign(GetLastErrorString());
357  return -ENOENT;
358  }
359 
360  for (;;) {
361  DWORD len;
362  char buf[64 << 10];
363  if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
364  err->assign(GetLastErrorString());
365  contents->clear();
366  return -1;
367  }
368  if (len == 0)
369  break;
370  contents->append(buf, len);
371  }
372  ::CloseHandle(f);
373  return 0;
374 #else
375  FILE* f = fopen(path.c_str(), "rb");
376  if (!f) {
377  err->assign(strerror(errno));
378  return -errno;
379  }
380 
381  char buf[64 << 10];
382  size_t len;
383  while ((len = fread(buf, 1, sizeof(buf), f)) > 0) {
384  contents->append(buf, len);
385  }
386  if (ferror(f)) {
387  err->assign(strerror(errno)); // XXX errno?
388  contents->clear();
389  fclose(f);
390  return -errno;
391  }
392  fclose(f);
393  return 0;
394 #endif
395 }
396 
397 void SetCloseOnExec(int fd) {
398 #ifndef _WIN32
399  int flags = fcntl(fd, F_GETFD);
400  if (flags < 0) {
401  perror("fcntl(F_GETFD)");
402  } else {
403  if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0)
404  perror("fcntl(F_SETFD)");
405  }
406 #else
407  HANDLE hd = (HANDLE) _get_osfhandle(fd);
408  if (! SetHandleInformation(hd, HANDLE_FLAG_INHERIT, 0)) {
409  fprintf(stderr, "SetHandleInformation(): %s", GetLastErrorString().c_str());
410  }
411 #endif // ! _WIN32
412 }
413 
414 
415 const char* SpellcheckStringV(const string& text,
416  const vector<const char*>& words) {
417  const bool kAllowReplacements = true;
418  const int kMaxValidEditDistance = 3;
419 
420  int min_distance = kMaxValidEditDistance + 1;
421  const char* result = NULL;
422  for (vector<const char*>::const_iterator i = words.begin();
423  i != words.end(); ++i) {
424  int distance = EditDistance(*i, text, kAllowReplacements,
425  kMaxValidEditDistance);
426  if (distance < min_distance) {
427  min_distance = distance;
428  result = *i;
429  }
430  }
431  return result;
432 }
433 
434 const char* SpellcheckString(const char* text, ...) {
435  // Note: This takes a const char* instead of a string& because using
436  // va_start() with a reference parameter is undefined behavior.
437  va_list ap;
438  va_start(ap, text);
439  vector<const char*> words;
440  const char* word;
441  while ((word = va_arg(ap, const char*)))
442  words.push_back(word);
443  va_end(ap);
444  return SpellcheckStringV(text, words);
445 }
446 
447 #ifdef _WIN32
448 string GetLastErrorString() {
449  DWORD err = GetLastError();
450 
451  char* msg_buf;
452  FormatMessageA(
453  FORMAT_MESSAGE_ALLOCATE_BUFFER |
454  FORMAT_MESSAGE_FROM_SYSTEM |
455  FORMAT_MESSAGE_IGNORE_INSERTS,
456  NULL,
457  err,
458  MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
459  (char*)&msg_buf,
460  0,
461  NULL);
462  string msg = msg_buf;
463  LocalFree(msg_buf);
464  return msg;
465 }
466 
467 void Win32Fatal(const char* function) {
468  Fatal("%s: %s", function, GetLastErrorString().c_str());
469 }
470 #endif
471 
472 static bool islatinalpha(int c) {
473  // isalpha() is locale-dependent.
474  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
475 }
476 
477 string StripAnsiEscapeCodes(const string& in) {
478  string stripped;
479  stripped.reserve(in.size());
480 
481  for (size_t i = 0; i < in.size(); ++i) {
482  if (in[i] != '\33') {
483  // Not an escape code.
484  stripped.push_back(in[i]);
485  continue;
486  }
487 
488  // Only strip CSIs for now.
489  if (i + 1 >= in.size()) break;
490  if (in[i + 1] != '[') continue; // Not a CSI.
491  i += 2;
492 
493  // Skip everything up to and including the next [a-zA-Z].
494  while (i < in.size() && !islatinalpha(in[i]))
495  ++i;
496  }
497  return stripped;
498 }
499 
501 #ifdef _WIN32
502  SYSTEM_INFO info;
503  GetNativeSystemInfo(&info);
504  return info.dwNumberOfProcessors;
505 #else
506  return sysconf(_SC_NPROCESSORS_ONLN);
507 #endif
508 }
509 
510 #if defined(_WIN32) || defined(__CYGWIN__)
511 static double CalculateProcessorLoad(uint64_t idle_ticks, uint64_t total_ticks)
512 {
513  static uint64_t previous_idle_ticks = 0;
514  static uint64_t previous_total_ticks = 0;
515  static double previous_load = -0.0;
516 
517  uint64_t idle_ticks_since_last_time = idle_ticks - previous_idle_ticks;
518  uint64_t total_ticks_since_last_time = total_ticks - previous_total_ticks;
519 
520  bool first_call = (previous_total_ticks == 0);
521  bool ticks_not_updated_since_last_call = (total_ticks_since_last_time == 0);
522 
523  double load;
524  if (first_call || ticks_not_updated_since_last_call) {
525  load = previous_load;
526  } else {
527  // Calculate load.
528  double idle_to_total_ratio =
529  ((double)idle_ticks_since_last_time) / total_ticks_since_last_time;
530  double load_since_last_call = 1.0 - idle_to_total_ratio;
531 
532  // Filter/smooth result when possible.
533  if(previous_load > 0) {
534  load = 0.9 * previous_load + 0.1 * load_since_last_call;
535  } else {
536  load = load_since_last_call;
537  }
538  }
539 
540  previous_load = load;
541  previous_total_ticks = total_ticks;
542  previous_idle_ticks = idle_ticks;
543 
544  return load;
545 }
546 
547 static uint64_t FileTimeToTickCount(const FILETIME & ft)
548 {
549  uint64_t high = (((uint64_t)(ft.dwHighDateTime)) << 32);
550  uint64_t low = ft.dwLowDateTime;
551  return (high | low);
552 }
553 
554 double GetLoadAverage() {
555  FILETIME idle_time, kernel_time, user_time;
556  BOOL get_system_time_succeeded =
557  GetSystemTimes(&idle_time, &kernel_time, &user_time);
558 
559  double posix_compatible_load;
560  if (get_system_time_succeeded) {
561  uint64_t idle_ticks = FileTimeToTickCount(idle_time);
562 
563  // kernel_time from GetSystemTimes already includes idle_time.
564  uint64_t total_ticks =
565  FileTimeToTickCount(kernel_time) + FileTimeToTickCount(user_time);
566 
567  double processor_load = CalculateProcessorLoad(idle_ticks, total_ticks);
568  posix_compatible_load = processor_load * GetProcessorCount();
569 
570  } else {
571  posix_compatible_load = -0.0;
572  }
573 
574  return posix_compatible_load;
575 }
576 #else
577 double GetLoadAverage() {
578  double loadavg[3] = { 0.0f, 0.0f, 0.0f };
579  if (getloadavg(loadavg, 3) < 0) {
580  // Maybe we should return an error here or the availability of
581  // getloadavg(3) should be checked when ninja is configured.
582  return -0.0f;
583  }
584  return loadavg[0];
585 }
586 #endif // _WIN32
587 
588 string ElideMiddle(const string& str, size_t width) {
589  const int kMargin = 3; // Space for "...".
590  string result = str;
591  if (result.size() + kMargin > width) {
592  size_t elide_size = (width - kMargin) / 2;
593  result = result.substr(0, elide_size)
594  + "..."
595  + result.substr(result.size() - elide_size, elide_size);
596  }
597  return result;
598 }
599 
600 bool Truncate(const string& path, size_t size, string* err) {
601 #ifdef _WIN32
602  int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
603  _S_IREAD | _S_IWRITE);
604  int success = _chsize(fh, size);
605  _close(fh);
606 #else
607  int success = truncate(path.c_str(), size);
608 #endif
609  // Both truncate() and _chsize() return 0 on success and set errno and return
610  // -1 on failure.
611  if (success < 0) {
612  *err = strerror(errno);
613  return false;
614  }
615  return true;
616 }
static bool StringNeedsShellEscaping(const string &input)
Definition: util.cc:267
const char * SpellcheckString(const char *text,...)
Like SpellcheckStringV, but takes a NULL-terminated list.
Definition: util.cc:434
void GetWin32EscapedString(const string &input, string *result)
Definition: util.cc:308
void GetShellEscapedString(const string &input, string *result)
Appends |input| to |*result|, escaping according to the whims of either Bash, or Win32's CommandLineT...
Definition: util.cc:281
bool CanonicalizePath(string *path, unsigned int *slash_bits, string *err)
Canonicalize a path like "foo/../bar.h" into just "bar.h".
Definition: util.cc:91
void SetCloseOnExec(int fd)
Mark a file descriptor to not be inherited on exec()s.
Definition: util.cc:397
static bool IsKnownWin32SafeCharacter(char ch)
Definition: util.cc:257
double GetLoadAverage()
Definition: util.cc:577
static bool StringNeedsWin32Escaping(const string &input)
Definition: util.cc:274
static bool islatinalpha(int c)
Definition: util.cc:472
int ReadFile(const string &path, string *contents, string *err)
Read a file to a string (in text mode: with CRLF conversion on Windows).
Definition: util.cc:343
#define METRIC_RECORD(name)
The primary interface to metrics.
Definition: metrics.h:85
static bool IsKnownShellSafeCharacter(char ch)
Definition: util.cc:240
bool Truncate(const string &path, size_t size, string *err)
Truncates a file to the given size.
Definition: util.cc:600
string StripAnsiEscapeCodes(const string &in)
Removes all Ansi escape codes (http://www.termsys.demon.co.uk/vtansi.htm).
Definition: util.cc:477
void Fatal(const char *msg,...)
Log a fatal message and exit.
Definition: util.cc:55
const char * SpellcheckStringV(const string &text, const vector< const char * > &words)
Given a misspelled string and a list of correct spellings, returns the closest match or NULL if there...
Definition: util.cc:415
int GetProcessorCount()
Definition: util.cc:500
unsigned long long uint64_t
Definition: win32port.h:22
void Warning(const char *msg,...)
Log a warning message.
Definition: util.cc:73
int EditDistance(const StringPiece &s1, const StringPiece &s2, bool allow_replacements, int max_edit_distance)
void Error(const char *msg,...)
Log an error message.
Definition: util.cc:82
string ElideMiddle(const string &str, size_t width)
Elide the given string str with '...' in the middle if the length exceeds width.
Definition: util.cc:588