1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3 * 4 * Copyright (c) 2013 David Chisnall 5 * All rights reserved. 6 * 7 * This software was developed by SRI International and the University of 8 * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) 9 * ("CTSRD"), as part of the DARPA CRASH research programme. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * $FreeBSD$ 33 */ 34 35 #include "input_buffer.hh" 36 #include <ctype.h> 37 #include <errno.h> 38 #include <limits.h> 39 #include <stdint.h> 40 #include <stdio.h> 41 #include <stdlib.h> 42 #include <string.h> 43 #include <functional> 44 #ifndef NDEBUG 45 #include <iostream> 46 #endif 47 48 49 #include <sys/stat.h> 50 #include <sys/mman.h> 51 #include <assert.h> 52 #include <fcntl.h> 53 #include <unistd.h> 54 55 #ifndef MAP_PREFAULT_READ 56 #define MAP_PREFAULT_READ 0 57 #endif 58 59 using std::string; 60 61 namespace 62 { 63 /** 64 * Subclass of input_buffer that mmap()s a file and owns the resulting memory. 65 * When this object is destroyed, the memory is unmapped. 66 */ 67 struct mmap_input_buffer : public dtc::input_buffer 68 { 69 string fn; 70 const string &filename() const override 71 { 72 return fn; 73 } 74 /** 75 * Constructs a new buffer from the file passed in as a file 76 * descriptor. 77 */ 78 mmap_input_buffer(int fd, string &&filename); 79 /** 80 * Unmaps the buffer, if one exists. 81 */ 82 virtual ~mmap_input_buffer(); 83 }; 84 /** 85 * Input buffer read from standard input. This is used for reading device tree 86 * blobs and source from standard input. It reads the entire input into 87 * malloc'd memory, so will be very slow for large inputs. DTS and DTB files 88 * are very rarely more than 10KB though, so this is probably not a problem. 89 */ 90 struct stream_input_buffer : public dtc::input_buffer 91 { 92 const string &filename() const override 93 { 94 static string n = "<standard input>"; 95 return n; 96 } 97 /** 98 * The buffer that will store the data read from the standard input. 99 */ 100 std::vector<char> b; 101 /** 102 * Constructs a new buffer from the standard input. 103 */ 104 stream_input_buffer(); 105 }; 106 107 mmap_input_buffer::mmap_input_buffer(int fd, string &&filename) 108 : input_buffer(0, 0), fn(filename) 109 { 110 struct stat sb; 111 if (fstat(fd, &sb)) 112 { 113 perror("Failed to stat file"); 114 } 115 size = sb.st_size; 116 buffer = (const char*)mmap(0, size, PROT_READ, MAP_PRIVATE | 117 MAP_PREFAULT_READ, fd, 0); 118 if (buffer == MAP_FAILED) 119 { 120 perror("Failed to mmap file"); 121 exit(EXIT_FAILURE); 122 } 123 } 124 125 mmap_input_buffer::~mmap_input_buffer() 126 { 127 if (buffer != 0) 128 { 129 munmap(const_cast<char*>(buffer), size); 130 } 131 } 132 133 stream_input_buffer::stream_input_buffer() : input_buffer(0, 0) 134 { 135 int c; 136 while ((c = fgetc(stdin)) != EOF) 137 { 138 b.push_back(c); 139 } 140 buffer = b.data(); 141 size = b.size(); 142 } 143 144 } // Anonymous namespace 145 146 147 namespace dtc 148 { 149 150 void 151 input_buffer::skip_to(char c) 152 { 153 while ((cursor < size) && (buffer[cursor] != c)) 154 { 155 cursor++; 156 } 157 } 158 159 void 160 text_input_buffer::skip_to(char c) 161 { 162 while (!finished() && (*(*this) != c)) 163 { 164 ++(*this); 165 } 166 } 167 168 void 169 text_input_buffer::skip_spaces() 170 { 171 if (finished()) { return; } 172 char c = *(*this); 173 bool last_nl = false; 174 while ((c == ' ') || (c == '\t') || (c == '\n') || (c == '\f') 175 || (c == '\v') || (c == '\r')) 176 { 177 last_nl = ((c == '\n') || (c == '\r')); 178 ++(*this); 179 if (finished()) 180 { 181 c = '\0'; 182 } 183 else 184 { 185 c = *(*this); 186 } 187 } 188 // Skip C preprocessor leftovers 189 if ((c == '#') && ((cursor == 0) || last_nl)) 190 { 191 skip_to('\n'); 192 skip_spaces(); 193 } 194 if (consume("/include/")) 195 { 196 handle_include(); 197 skip_spaces(); 198 } 199 } 200 201 void 202 text_input_buffer::handle_include() 203 { 204 bool reallyInclude = true; 205 if (consume("if ")) 206 { 207 next_token(); 208 string name = parse_property_name(); 209 if (defines.count(name) == 0) 210 { 211 reallyInclude = false; 212 } 213 consume('/'); 214 } 215 next_token(); 216 if (!consume('"')) 217 { 218 parse_error("Expected quoted filename"); 219 return; 220 } 221 auto loc = location(); 222 string file = parse_to('"'); 223 consume('"'); 224 if (!reallyInclude) 225 { 226 return; 227 } 228 string include_file = dir + '/' + file; 229 auto include_buffer = input_buffer::buffer_for_file(include_file, false); 230 if (include_buffer == 0) 231 { 232 for (auto i : include_paths) 233 { 234 include_file = i + '/' + file; 235 include_buffer = input_buffer::buffer_for_file(include_file, false); 236 if (include_buffer != 0) 237 { 238 break; 239 } 240 } 241 } 242 if (depfile) 243 { 244 putc(' ', depfile); 245 fputs(include_file.c_str(), depfile); 246 } 247 if (!include_buffer) 248 { 249 loc.report_error("Unable to locate input file"); 250 return; 251 } 252 input_stack.push(std::move(include_buffer)); 253 } 254 255 bool text_input_buffer::read_binary_file(const std::string &filename, byte_buffer &b) 256 { 257 bool try_include_paths = true; 258 string include_file; 259 if (filename[0] == '/') 260 { 261 include_file = filename; 262 // Don't try include paths if we're given an absolute path. 263 // Failing is better so that we don't accidentally do the wrong thing, 264 // but make it seem like everything is alright. 265 try_include_paths = false; 266 } 267 else 268 { 269 include_file = dir + '/' + filename; 270 } 271 auto include_buffer = input_buffer::buffer_for_file(include_file, false); 272 if (include_buffer == 0 && try_include_paths) 273 { 274 for (auto i : include_paths) 275 { 276 include_file = i + '/' + filename; 277 include_buffer = input_buffer::buffer_for_file(include_file, false); 278 if (include_buffer != 0) 279 { 280 break; 281 } 282 } 283 } 284 if (!include_buffer) 285 { 286 return false; 287 } 288 if (depfile) 289 { 290 putc(' ', depfile); 291 fputs(include_file.c_str(), depfile); 292 } 293 b.insert(b.begin(), include_buffer->begin(), include_buffer->end()); 294 return true; 295 } 296 297 input_buffer 298 input_buffer::buffer_from_offset(int offset, int s) 299 { 300 if (offset < 0) 301 { 302 return input_buffer(); 303 } 304 if (s == 0) 305 { 306 s = size - offset; 307 } 308 if (offset > size) 309 { 310 return input_buffer(); 311 } 312 if (s > (size-offset)) 313 { 314 return input_buffer(); 315 } 316 return input_buffer(&buffer[offset], s); 317 } 318 319 bool 320 input_buffer::consume(const char *str) 321 { 322 int len = strlen(str); 323 if (len > size - cursor) 324 { 325 return false; 326 } 327 else 328 { 329 for (int i=0 ; i<len ; ++i) 330 { 331 if (str[i] != (*this)[i]) 332 { 333 return false; 334 } 335 } 336 cursor += len; 337 return true; 338 } 339 return false; 340 } 341 342 bool 343 input_buffer::consume_integer(unsigned long long &outInt) 344 { 345 // The first character must be a digit. Hex and octal strings 346 // are prefixed by 0 and 0x, respectively. 347 if (!isdigit((*this)[0])) 348 { 349 return false; 350 } 351 char *end= const_cast<char*>(&buffer[size]); 352 outInt = strtoull(&buffer[cursor], &end, 0); 353 if (end == &buffer[cursor]) 354 { 355 return false; 356 } 357 cursor = end - buffer; 358 return true; 359 } 360 361 namespace { 362 363 /** 364 * Convenience typedef for the type that we use for all values. 365 */ 366 typedef unsigned long long valty; 367 368 /** 369 * Expression tree currently being parsed. 370 */ 371 struct expression 372 { 373 typedef text_input_buffer::source_location source_location; 374 /** 375 * The type that is returned when computing the result. The boolean value 376 * indicates whether this is a valid expression. 377 * 378 * FIXME: Once we can use C++17, this should be `std::optional`. 379 */ 380 typedef std::pair<valty, bool> result; 381 /** 382 * Evaluate this node, taking into account operator precedence. 383 */ 384 virtual result operator()() = 0; 385 /** 386 * Returns the precedence of this node. Lower values indicate higher 387 * precedence. 388 */ 389 virtual int precedence() = 0; 390 /** 391 * Constructs an expression, storing the location where it was created. 392 */ 393 expression(source_location l) : loc(l) {} 394 virtual ~expression() {} 395 #ifndef NDEBUG 396 /** 397 * Dumps this expression to `std::cerr`, appending a newline if `nl` is 398 * `true`. 399 */ 400 void dump(bool nl=false) 401 { 402 void *ptr = this; 403 if (ptr == nullptr) 404 { 405 std::cerr << "{nullptr}\n"; 406 return; 407 } 408 dump_impl(); 409 if (nl) 410 { 411 std::cerr << '\n'; 412 } 413 } 414 private: 415 /** 416 * Method that sublcasses override to implement the behaviour of `dump()`. 417 */ 418 virtual void dump_impl() = 0; 419 #endif 420 protected: 421 source_location loc; 422 }; 423 424 /** 425 * Expression wrapping a single integer. Leaf nodes in the expression tree. 426 */ 427 class terminal_expr : public expression 428 { 429 /** 430 * The value that this wraps. 431 */ 432 valty val; 433 /** 434 * Evaluate. Trivially returns the value that this class wraps. 435 */ 436 result operator()() override 437 { 438 return {val, true}; 439 } 440 int precedence() override 441 { 442 return 0; 443 } 444 public: 445 /** 446 * Constructor. 447 */ 448 terminal_expr(source_location l, valty v) : expression(l), val(v) {} 449 #ifndef NDEBUG 450 void dump_impl() override { std::cerr << val; } 451 #endif 452 }; 453 454 /** 455 * Parenthetical expression. Exists to make the contents opaque. 456 */ 457 struct paren_expression : public expression 458 { 459 /** 460 * The expression within the parentheses. 461 */ 462 expression_ptr subexpr; 463 /** 464 * Constructor. Takes the child expression as the only argument. 465 */ 466 paren_expression(source_location l, expression_ptr p) : expression(l), 467 subexpr(std::move(p)) {} 468 int precedence() override 469 { 470 return 0; 471 } 472 /** 473 * Evaluate - just forwards to the underlying expression. 474 */ 475 result operator()() override 476 { 477 return (*subexpr)(); 478 } 479 #ifndef NDEBUG 480 void dump_impl() override 481 { 482 std::cerr << " ("; 483 subexpr->dump(); 484 std::cerr << ") "; 485 } 486 #endif 487 }; 488 489 /** 490 * Template class for unary operators. The `OpChar` template parameter is 491 * solely for debugging and makes it easy to print the expression. The `Op` 492 * template parameter is a function object that implements the operator that 493 * this class provides. Most of these are provided by the `<functional>` 494 * header. 495 */ 496 template<char OpChar, class Op> 497 class unary_operator : public expression 498 { 499 /** 500 * The subexpression for this unary operator. 501 */ 502 expression_ptr subexpr; 503 result operator()() override 504 { 505 Op op; 506 result s = (*subexpr)(); 507 if (!s.second) 508 { 509 return s; 510 } 511 return {op(s.first), true}; 512 } 513 /** 514 * All unary operators have the same precedence. They are all evaluated 515 * before binary expressions, but after parentheses. 516 */ 517 int precedence() override 518 { 519 return 3; 520 } 521 public: 522 unary_operator(source_location l, expression_ptr p) : 523 expression(l), subexpr(std::move(p)) {} 524 #ifndef NDEBUG 525 void dump_impl() override 526 { 527 std::cerr << OpChar; 528 subexpr->dump(); 529 } 530 #endif 531 }; 532 533 /** 534 * Abstract base class for binary operators. Allows the tree to be modified 535 * without knowing what the operations actually are. 536 */ 537 struct binary_operator_base : public expression 538 { 539 using expression::expression; 540 /** 541 * The left side of the expression. 542 */ 543 expression_ptr lhs; 544 /** 545 * The right side of the expression. 546 */ 547 expression_ptr rhs; 548 /** 549 * Insert a node somewhere down the path of left children, until it would 550 * be preempting something that should execute first. 551 */ 552 void insert_left(binary_operator_base *new_left) 553 { 554 if (lhs->precedence() < new_left->precedence()) 555 { 556 new_left->rhs = std::move(lhs); 557 lhs.reset(new_left); 558 } 559 else 560 { 561 static_cast<binary_operator_base*>(lhs.get())->insert_left(new_left); 562 } 563 } 564 }; 565 566 /** 567 * Template class for binary operators. The precedence and the operation are 568 * provided as template parameters. 569 */ 570 template<int Precedence, class Op> 571 struct binary_operator : public binary_operator_base 572 { 573 result operator()() override 574 { 575 Op op; 576 result l = (*lhs)(); 577 result r = (*rhs)(); 578 if (!(l.second && r.second)) 579 { 580 return {0, false}; 581 } 582 return {op(l.first, r.first), true}; 583 } 584 int precedence() override 585 { 586 return Precedence; 587 } 588 #ifdef NDEBUG 589 /** 590 * Constructor. Takes the name of the operator as an argument, for 591 * debugging. Only stores it in debug mode. 592 */ 593 binary_operator(source_location l, const char *) : 594 binary_operator_base(l) {} 595 #else 596 const char *opName; 597 binary_operator(source_location l, const char *o) : 598 binary_operator_base(l), opName(o) {} 599 void dump_impl() override 600 { 601 lhs->dump(); 602 std::cerr << opName; 603 rhs->dump(); 604 } 605 #endif 606 }; 607 608 /** 609 * Ternary conditional operators (`cond ? true : false`) are a special case - 610 * there are no other ternary operators. 611 */ 612 class ternary_conditional_operator : public expression 613 { 614 /** 615 * The condition for the clause. 616 */ 617 expression_ptr cond; 618 /** 619 * The expression that this evaluates to if the condition is true. 620 */ 621 expression_ptr lhs; 622 /** 623 * The expression that this evaluates to if the condition is false. 624 */ 625 expression_ptr rhs; 626 result operator()() override 627 { 628 result c = (*cond)(); 629 result l = (*lhs)(); 630 result r = (*rhs)(); 631 if (!(l.second && r.second && c.second)) 632 { 633 return {0, false}; 634 } 635 return c.first ? l : r; 636 } 637 int precedence() override 638 { 639 // The actual precedence of a ternary conditional operator is 15, but 640 // its associativity is the opposite way around to the other operators, 641 // so we fudge it slightly. 642 return 3; 643 } 644 #ifndef NDEBUG 645 void dump_impl() override 646 { 647 cond->dump(); 648 std::cerr << " ? "; 649 lhs->dump(); 650 std::cerr << " : "; 651 rhs->dump(); 652 } 653 #endif 654 public: 655 ternary_conditional_operator(source_location sl, 656 expression_ptr c, 657 expression_ptr l, 658 expression_ptr r) : 659 expression(sl), cond(std::move(c)), lhs(std::move(l)), 660 rhs(std::move(r)) {} 661 }; 662 663 template<typename T> 664 struct lshift 665 { 666 constexpr T operator()(const T &lhs, const T &rhs) const 667 { 668 return lhs << rhs; 669 } 670 }; 671 template<typename T> 672 struct rshift 673 { 674 constexpr T operator()(const T &lhs, const T &rhs) const 675 { 676 return lhs >> rhs; 677 } 678 }; 679 template<typename T> 680 struct unary_plus 681 { 682 constexpr T operator()(const T &val) const 683 { 684 return +val; 685 } 686 }; 687 // TODO: Replace with std::bit_not once we can guarantee C++14 as a baseline. 688 template<typename T> 689 struct bit_not 690 { 691 constexpr T operator()(const T &val) const 692 { 693 return ~val; 694 } 695 }; 696 697 template<typename T> 698 struct divmod : public binary_operator<5, T> 699 { 700 using binary_operator<5, T>::binary_operator; 701 using typename binary_operator_base::result; 702 result operator()() override 703 { 704 result r = (*binary_operator_base::rhs)(); 705 if (r.second && (r.first == 0)) 706 { 707 expression::loc.report_error("Division by zero"); 708 return {0, false}; 709 } 710 return binary_operator<5, T>::operator()(); 711 } 712 }; 713 714 } // anonymous namespace 715 716 717 expression_ptr text_input_buffer::parse_binary_expression(expression_ptr lhs) 718 { 719 next_token(); 720 binary_operator_base *expr = nullptr; 721 char op = *(*this); 722 source_location l = location(); 723 switch (op) 724 { 725 default: 726 return lhs; 727 case '+': 728 expr = new binary_operator<6, std::plus<valty>>(l, "+"); 729 break; 730 case '-': 731 expr = new binary_operator<6, std::minus<valty>>(l, "-"); 732 break; 733 case '%': 734 expr = new divmod<std::modulus<valty>>(l, "/"); 735 break; 736 case '*': 737 expr = new binary_operator<5, std::multiplies<valty>>(l, "*"); 738 break; 739 case '/': 740 expr = new divmod<std::divides<valty>>(l, "/"); 741 break; 742 case '<': 743 switch (peek()) 744 { 745 default: 746 parse_error("Invalid operator"); 747 return nullptr; 748 case ' ': 749 case '(': 750 case '0'...'9': 751 expr = new binary_operator<8, std::less<valty>>(l, "<"); 752 break; 753 case '=': 754 ++(*this); 755 expr = new binary_operator<8, std::less_equal<valty>>(l, "<="); 756 break; 757 case '<': 758 ++(*this); 759 expr = new binary_operator<7, lshift<valty>>(l, "<<"); 760 break; 761 } 762 break; 763 case '>': 764 switch (peek()) 765 { 766 default: 767 parse_error("Invalid operator"); 768 return nullptr; 769 case '(': 770 case ' ': 771 case '0'...'9': 772 expr = new binary_operator<8, std::greater<valty>>(l, ">"); 773 break; 774 case '=': 775 ++(*this); 776 expr = new binary_operator<8, std::greater_equal<valty>>(l, ">="); 777 break; 778 case '>': 779 ++(*this); 780 expr = new binary_operator<7, rshift<valty>>(l, ">>"); 781 break; 782 return lhs; 783 } 784 break; 785 case '=': 786 if (peek() != '=') 787 { 788 parse_error("Invalid operator"); 789 return nullptr; 790 } 791 expr = new binary_operator<9, std::equal_to<valty>>(l, "=="); 792 break; 793 case '!': 794 if (peek() != '=') 795 { 796 parse_error("Invalid operator"); 797 return nullptr; 798 } 799 cursor++; 800 expr = new binary_operator<9, std::not_equal_to<valty>>(l, "!="); 801 break; 802 case '&': 803 if (peek() == '&') 804 { 805 expr = new binary_operator<13, std::logical_and<valty>>(l, "&&"); 806 } 807 else 808 { 809 expr = new binary_operator<10, std::bit_and<valty>>(l, "&"); 810 } 811 break; 812 case '|': 813 if (peek() == '|') 814 { 815 expr = new binary_operator<12, std::logical_or<valty>>(l, "||"); 816 } 817 else 818 { 819 expr = new binary_operator<14, std::bit_or<valty>>(l, "|"); 820 } 821 break; 822 case '?': 823 { 824 consume('?'); 825 expression_ptr true_case = parse_expression(); 826 next_token(); 827 if (!true_case || !consume(':')) 828 { 829 parse_error("Expected : in ternary conditional operator"); 830 return nullptr; 831 } 832 expression_ptr false_case = parse_expression(); 833 if (!false_case) 834 { 835 parse_error("Expected false condition for ternary operator"); 836 return nullptr; 837 } 838 return expression_ptr(new ternary_conditional_operator(l, std::move(lhs), 839 std::move(true_case), std::move(false_case))); 840 } 841 } 842 ++(*this); 843 next_token(); 844 expression_ptr e(expr); 845 expression_ptr rhs(parse_expression()); 846 if (!rhs) 847 { 848 return nullptr; 849 } 850 expr->lhs = std::move(lhs); 851 if (rhs->precedence() < expr->precedence()) 852 { 853 expr->rhs = std::move(rhs); 854 } 855 else 856 { 857 // If we're a normal left-to-right expression, then we need to insert 858 // this as the far-left child node of the rhs expression 859 binary_operator_base *rhs_op = 860 static_cast<binary_operator_base*>(rhs.get()); 861 rhs_op->insert_left(expr); 862 e.release(); 863 return rhs; 864 } 865 return e; 866 } 867 868 expression_ptr text_input_buffer::parse_expression(bool stopAtParen) 869 { 870 next_token(); 871 unsigned long long leftVal; 872 expression_ptr lhs; 873 source_location l = location(); 874 switch (*(*this)) 875 { 876 case '0'...'9': 877 if (!consume_integer(leftVal)) 878 { 879 return nullptr; 880 } 881 lhs.reset(new terminal_expr(l, leftVal)); 882 break; 883 case '(': 884 { 885 consume('('); 886 expression_ptr &&subexpr = parse_expression(); 887 if (!subexpr) 888 { 889 return nullptr; 890 } 891 lhs.reset(new paren_expression(l, std::move(subexpr))); 892 if (!consume(')')) 893 { 894 return nullptr; 895 } 896 if (stopAtParen) 897 { 898 return lhs; 899 } 900 break; 901 } 902 case '+': 903 { 904 consume('+'); 905 expression_ptr &&subexpr = parse_expression(); 906 if (!subexpr) 907 { 908 return nullptr; 909 } 910 lhs.reset(new unary_operator<'+', unary_plus<valty>>(l, std::move(subexpr))); 911 break; 912 } 913 case '-': 914 { 915 consume('-'); 916 expression_ptr &&subexpr = parse_expression(); 917 if (!subexpr) 918 { 919 return nullptr; 920 } 921 lhs.reset(new unary_operator<'-', std::negate<valty>>(l, std::move(subexpr))); 922 break; 923 } 924 case '!': 925 { 926 consume('!'); 927 expression_ptr &&subexpr = parse_expression(); 928 if (!subexpr) 929 { 930 return nullptr; 931 } 932 lhs.reset(new unary_operator<'!', std::logical_not<valty>>(l, std::move(subexpr))); 933 break; 934 } 935 case '~': 936 { 937 consume('~'); 938 expression_ptr &&subexpr = parse_expression(); 939 if (!subexpr) 940 { 941 return nullptr; 942 } 943 lhs.reset(new unary_operator<'~', bit_not<valty>>(l, std::move(subexpr))); 944 break; 945 } 946 } 947 if (!lhs) 948 { 949 return nullptr; 950 } 951 return parse_binary_expression(std::move(lhs)); 952 } 953 954 bool 955 text_input_buffer::consume_integer_expression(unsigned long long &outInt) 956 { 957 switch (*(*this)) 958 { 959 case '(': 960 { 961 expression_ptr e(parse_expression(true)); 962 if (!e) 963 { 964 return false; 965 } 966 auto r = (*e)(); 967 if (r.second) 968 { 969 outInt = r.first; 970 return true; 971 } 972 return false; 973 } 974 case '0'...'9': 975 return consume_integer(outInt); 976 default: 977 return false; 978 } 979 } 980 981 bool 982 input_buffer::consume_hex_byte(uint8_t &outByte) 983 { 984 if (!ishexdigit((*this)[0]) && !ishexdigit((*this)[1])) 985 { 986 return false; 987 } 988 outByte = (digittoint((*this)[0]) << 4) | digittoint((*this)[1]); 989 cursor += 2; 990 return true; 991 } 992 993 text_input_buffer& 994 text_input_buffer::next_token() 995 { 996 auto &self = *this; 997 int start; 998 do { 999 start = cursor; 1000 skip_spaces(); 1001 if (finished()) 1002 { 1003 return self; 1004 } 1005 // Parse /* comments 1006 if (*self == '/' && peek() == '*') 1007 { 1008 // eat the start of the comment 1009 ++self; 1010 ++self; 1011 do { 1012 // Find the ending * of */ 1013 while ((*self != '\0') && (*self != '*') && !finished()) 1014 { 1015 ++self; 1016 } 1017 // Eat the * 1018 ++self; 1019 } while ((*self != '\0') && (*self != '/') && !finished()); 1020 // Eat the / 1021 ++self; 1022 } 1023 // Parse // comments 1024 if ((*self == '/' && peek() == '/')) 1025 { 1026 // eat the start of the comment 1027 ++self; 1028 ++self; 1029 // Find the ending of the line 1030 while (*self != '\n' && !finished()) 1031 { 1032 ++self; 1033 } 1034 // Eat the \n 1035 ++self; 1036 } 1037 } while (start != cursor); 1038 return self; 1039 } 1040 1041 void 1042 text_input_buffer::parse_error(const char *msg) 1043 { 1044 if (input_stack.empty()) 1045 { 1046 fprintf(stderr, "Error: %s\n", msg); 1047 return; 1048 } 1049 input_buffer &b = *input_stack.top(); 1050 parse_error(msg, b, b.cursor); 1051 } 1052 void 1053 text_input_buffer::parse_error(const char *msg, 1054 input_buffer &b, 1055 int loc) 1056 { 1057 int line_count = 1; 1058 int line_start = 0; 1059 int line_end = loc; 1060 if (loc < 0 || loc > b.size) 1061 { 1062 return; 1063 } 1064 for (int i=loc ; i>0 ; --i) 1065 { 1066 if (b.buffer[i] == '\n') 1067 { 1068 line_count++; 1069 if (line_start == 0) 1070 { 1071 line_start = i+1; 1072 } 1073 } 1074 } 1075 for (int i=loc+1 ; i<b.size ; ++i) 1076 { 1077 if (b.buffer[i] == '\n') 1078 { 1079 line_end = i; 1080 break; 1081 } 1082 } 1083 fprintf(stderr, "Error at %s:%d:%d: %s\n", b.filename().c_str(), line_count, loc - line_start, msg); 1084 fwrite(&b.buffer[line_start], line_end-line_start, 1, stderr); 1085 putc('\n', stderr); 1086 for (int i=0 ; i<(loc-line_start) ; ++i) 1087 { 1088 char c = (b.buffer[i+line_start] == '\t') ? '\t' : ' '; 1089 putc(c, stderr); 1090 } 1091 putc('^', stderr); 1092 putc('\n', stderr); 1093 } 1094 #ifndef NDEBUG 1095 void 1096 input_buffer::dump() 1097 { 1098 fprintf(stderr, "Current cursor: %d\n", cursor); 1099 fwrite(&buffer[cursor], size-cursor, 1, stderr); 1100 } 1101 #endif 1102 1103 1104 namespace 1105 { 1106 /** 1107 * The source files are ASCII, so we provide a non-locale-aware version of 1108 * isalpha. This is a class so that it can be used with a template function 1109 * for parsing strings. 1110 */ 1111 struct is_alpha 1112 { 1113 static inline bool check(const char c) 1114 { 1115 return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && 1116 (c <= 'Z')); 1117 } 1118 }; 1119 /** 1120 * Check whether a character is in the set allowed for node names. This is a 1121 * class so that it can be used with a template function for parsing strings. 1122 */ 1123 struct is_node_name_character 1124 { 1125 static inline bool check(const char c) 1126 { 1127 switch(c) 1128 { 1129 default: 1130 return false; 1131 case 'a'...'z': case 'A'...'Z': case '0'...'9': 1132 case ',': case '.': case '+': case '-': 1133 case '_': 1134 return true; 1135 } 1136 } 1137 }; 1138 /** 1139 * Check whether a character is in the set allowed for property names. This is 1140 * a class so that it can be used with a template function for parsing strings. 1141 */ 1142 struct is_property_name_character 1143 { 1144 static inline bool check(const char c) 1145 { 1146 switch(c) 1147 { 1148 default: 1149 return false; 1150 case 'a'...'z': case 'A'...'Z': case '0'...'9': 1151 case ',': case '.': case '+': case '-': 1152 case '_': case '#': 1153 return true; 1154 } 1155 } 1156 }; 1157 1158 template<class T> 1159 string parse(text_input_buffer &s) 1160 { 1161 std::vector<char> bytes; 1162 for (char c=*s ; T::check(c) ; c=*(++s)) 1163 { 1164 bytes.push_back(c); 1165 } 1166 return string(bytes.begin(), bytes.end()); 1167 } 1168 1169 } 1170 1171 string 1172 text_input_buffer::parse_node_name() 1173 { 1174 return parse<is_node_name_character>(*this); 1175 } 1176 1177 string 1178 text_input_buffer::parse_property_name() 1179 { 1180 return parse<is_property_name_character>(*this); 1181 } 1182 1183 string 1184 text_input_buffer::parse_node_or_property_name(bool &is_property) 1185 { 1186 if (is_property) 1187 { 1188 return parse_property_name(); 1189 } 1190 std::vector<char> bytes; 1191 for (char c=*(*this) ; is_node_name_character::check(c) ; c=*(++(*this))) 1192 { 1193 bytes.push_back(c); 1194 } 1195 for (char c=*(*this) ; is_property_name_character::check(c) ; c=*(++(*this))) 1196 { 1197 bytes.push_back(c); 1198 is_property = true; 1199 } 1200 return string(bytes.begin(), bytes.end()); 1201 } 1202 1203 string 1204 input_buffer::parse_to(char stop) 1205 { 1206 std::vector<char> bytes; 1207 for (char c=*(*this) ; c != stop ; c=*(++(*this))) 1208 { 1209 bytes.push_back(c); 1210 } 1211 return string(bytes.begin(), bytes.end()); 1212 } 1213 1214 string 1215 text_input_buffer::parse_to(char stop) 1216 { 1217 std::vector<char> bytes; 1218 for (char c=*(*this) ; c != stop ; c=*(++(*this))) 1219 { 1220 if (finished()) 1221 { 1222 break; 1223 } 1224 bytes.push_back(c); 1225 } 1226 return string(bytes.begin(), bytes.end()); 1227 } 1228 1229 char 1230 text_input_buffer::peek() 1231 { 1232 return (*input_stack.top())[1]; 1233 } 1234 1235 std::unique_ptr<input_buffer> 1236 input_buffer::buffer_for_file(const string &path, bool warn) 1237 { 1238 if (path == "-") 1239 { 1240 std::unique_ptr<input_buffer> b(new stream_input_buffer()); 1241 return b; 1242 } 1243 int source = open(path.c_str(), O_RDONLY); 1244 if (source == -1) 1245 { 1246 if (warn) 1247 { 1248 fprintf(stderr, "Unable to open file '%s'. %s\n", path.c_str(), strerror(errno)); 1249 } 1250 return 0; 1251 } 1252 struct stat st; 1253 if (fstat(source, &st) == 0 && S_ISDIR(st.st_mode)) 1254 { 1255 if (warn) 1256 { 1257 fprintf(stderr, "File %s is a directory\n", path.c_str()); 1258 } 1259 close(source); 1260 return 0; 1261 } 1262 std::unique_ptr<input_buffer> b(new mmap_input_buffer(source, string(path))); 1263 close(source); 1264 return b; 1265 } 1266 1267 } // namespace dtc 1268 1269