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