From owner-svn-src-all@freebsd.org Tue Dec 29 16:29:44 2015 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 77992A5523C; Tue, 29 Dec 2015 16:29:44 +0000 (UTC) (envelope-from theraven@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 44112111D; Tue, 29 Dec 2015 16:29:44 +0000 (UTC) (envelope-from theraven@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id tBTGThpv093345; Tue, 29 Dec 2015 16:29:43 GMT (envelope-from theraven@FreeBSD.org) Received: (from theraven@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id tBTGTgf8093337; Tue, 29 Dec 2015 16:29:42 GMT (envelope-from theraven@FreeBSD.org) Message-Id: <201512291629.tBTGTgf8093337@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: theraven set sender to theraven@FreeBSD.org using -f From: David Chisnall Date: Tue, 29 Dec 2015 16:29:42 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r292876 - head/usr.bin/dtc X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 29 Dec 2015 16:29:44 -0000 Author: theraven Date: Tue Dec 29 16:29:42 2015 New Revision: 292876 URL: https://svnweb.freebsd.org/changeset/base/292876 Log: Improvements to BSD-licensed DTC. - Added an expression parser so that expressions from headers are now working - Fixed missing null terminators on cross references - Disabled exceptions / RTTI in the build for smaller binaries - Changed phandle order generation to be identical to GPL'd dtc Modified: head/usr.bin/dtc/Makefile head/usr.bin/dtc/checking.cc head/usr.bin/dtc/checking.hh head/usr.bin/dtc/dtb.hh head/usr.bin/dtc/fdt.cc head/usr.bin/dtc/fdt.hh head/usr.bin/dtc/input_buffer.cc head/usr.bin/dtc/input_buffer.hh Modified: head/usr.bin/dtc/Makefile ============================================================================== --- head/usr.bin/dtc/Makefile Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/Makefile Tue Dec 29 16:29:42 2015 (r292876) @@ -6,7 +6,7 @@ MAN= dtc.1 WARNS?= 3 -CXXFLAGS+= -std=c++11 +CXXFLAGS+= -std=c++11 -fno-rtti -fno-exceptions NO_SHARED?=NO Modified: head/usr.bin/dtc/checking.cc ============================================================================== --- head/usr.bin/dtc/checking.cc Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/checking.cc Tue Dec 29 16:29:42 2015 (r292876) @@ -51,7 +51,7 @@ namespace struct address_cells_checker : public checker { address_cells_checker(const char *name) : checker(name) {} - virtual bool check_node(device_tree *tree, const node_ptr &n) + virtual bool check_node(device_tree *, const node_ptr &n) { // If this has no children, it trivially meets the // conditions. @@ -151,7 +151,7 @@ property_checker::check_property(device_ } bool -property_size_checker::check(device_tree *tree, const node_ptr &n, property_ptr p) +property_size_checker::check(device_tree *, const node_ptr &, property_ptr p) { uint32_t psize = 0; for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i) Modified: head/usr.bin/dtc/checking.hh ============================================================================== --- head/usr.bin/dtc/checking.hh Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/checking.hh Tue Dec 29 16:29:42 2015 (r292876) @@ -86,7 +86,7 @@ class checker * Method for checking that a node is valid. The root class version * does nothing, subclasses should override this. */ - virtual bool check_node(device_tree *tree, const node_ptr &n) + virtual bool check_node(device_tree *, const node_ptr &) { return true; } @@ -94,7 +94,7 @@ class checker * Method for checking that a property is valid. The root class * version does nothing, subclasses should override this. */ - virtual bool check_property(device_tree *tree, const node_ptr &n, property_ptr p) + virtual bool check_property(device_tree *, const node_ptr &, property_ptr ) { return true; } @@ -160,7 +160,7 @@ struct property_type_checker begin() == p->end(); } @@ -175,7 +175,7 @@ struct property_type_checker begin() + 1 == p->end()) && p->begin()->is_string(); } @@ -190,7 +190,7 @@ struct property_type_checker begin(),e=p->end() ; i!=e ; ++i) @@ -213,7 +213,7 @@ struct property_type_checker begin() + 1 == p->end()) && (tree->referenced_node(*p->begin()) != 0); Modified: head/usr.bin/dtc/dtb.hh ============================================================================== --- head/usr.bin/dtc/dtb.hh Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/dtb.hh Tue Dec 29 16:29:42 2015 (r292876) @@ -186,11 +186,11 @@ class binary_writer : public output_writ * The binary format does not support labels, so this method * does nothing. */ - virtual void write_label(string name) {} + virtual void write_label(string) {} /** * Comments are ignored by the binary writer. */ - virtual void write_comment(string name) {} + virtual void write_comment(string) {} virtual void write_string(string name); virtual void write_data(uint8_t v); virtual void write_data(uint32_t v); Modified: head/usr.bin/dtc/fdt.cc ============================================================================== --- head/usr.bin/dtc/fdt.cc Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/fdt.cc Tue Dec 29 16:29:42 2015 (r292876) @@ -264,24 +264,6 @@ property::parse_string(input_buffer &inp void property::parse_cells(input_buffer &input, int cell_size) { - unsigned long long cell_max; - switch (cell_size) - { - case 8: - cell_max = UINT8_MAX; - break; - case 16: - cell_max = UINT16_MAX; - break; - case 32: - cell_max = UINT32_MAX; - break; - case 64: - cell_max = UINT64_MAX; - break; - default: - assert(0 && "Invalid cell size!"); - } assert(input[0] == '<'); ++input; property_value v; @@ -327,19 +309,12 @@ property::parse_cells(input_buffer &inpu //FIXME: We should support labels in the middle //of these, but we don't. unsigned long long val; - if (!input.consume_integer(val)) + if (!input.consume_integer_expression(val)) { input.parse_error("Expected numbers in array of cells"); valid = false; return; } - if (val > cell_max) - { - fprintf(stderr, "%lld > %lld\n", val, cell_max); - input.parse_error("Value out of range"); - valid = false; - return; - } switch (cell_size) { case 8: @@ -685,6 +660,16 @@ node::parse_name(input_buffer &input, bo return n; } +void +node::visit(std::function fn) +{ + fn(*this); + for (auto &&c : children) + { + c->visit(fn); + } +} + node::node(input_buffer &structs, input_buffer &strings) : valid(true) { const char *name_start = (const char*)structs; @@ -742,7 +727,7 @@ node::node(input_buffer &structs, input_ valid = false; return; } - properties.push_back(prop); + props.push_back(prop); break; } break; @@ -806,7 +791,7 @@ node::node(input_buffer &input, string n } else { - properties.push_back(p); + props.push_back(p); } } else if (!is_property && input[0] == ('{')) @@ -824,7 +809,7 @@ node::node(input_buffer &input, string n } else if (input.consume(';')) { - properties.push_back(property_ptr(new property(child_name, child_label))); + props.push_back(property_ptr(new property(child_name, child_label))); } else { @@ -857,9 +842,9 @@ node::sort() { std::sort(property_begin(), property_end(), cmp_properties); std::sort(child_begin(), child_end(), cmp_children); - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->sort(); + c->sort(); } } @@ -892,7 +877,7 @@ node::parse_dtb(input_buffer &structs, i property_ptr node::get_property(string key) { - for (auto &i : properties) + for (auto &i : props) { if (i->get_key() == key) { @@ -914,14 +899,14 @@ node::merge_node(node_ptr other) // large numbers of properties, but for typical usage the // entire vector will fit (easily) into cache, so iterating // over it repeatedly isn't that expensive. - for (auto &p : other->properties) + for (auto &p : other->properties()) { bool found = false; - for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto &mp : properties()) { - if ((*i)->get_key() == p->get_key()) + if (mp->get_key() == p->get_key()) { - *i = p; + mp = p; found = true; break; } @@ -964,13 +949,13 @@ node::write(dtb::output_writer &writer, writer.write_comment(name); writer.write_data(name_buffer); writer.write_data((uint8_t)0); - for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto p : properties()) { - (*i)->write(writer, strings); + p->write(writer, strings); } - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->write(writer, strings); + c->write(writer, strings); } writer.write_token(dtb::FDT_END_NODE); } @@ -999,13 +984,13 @@ node::write_dts(FILE *file, int indent) unit_address.print(file); } fputs(" {\n\n", file); - for (auto i=property_begin(), e=property_end() ; i!=e ; ++i) + for (auto p : properties()) { - (*i)->write_dts(file, indent+1); + p->write_dts(file, indent+1); } - for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i) + for (auto &c : child_nodes()) { - (*i)->write_dts(file, indent+1); + c->write_dts(file, indent+1); } for (int i=0 ; ichild_begin(), e=n->child_end() ; i!=e ; ++i) + for (auto &c : n->child_nodes()) { - collect_names_recursive(*i, path); + collect_names_recursive(c, path); } path.pop_back(); // Now we collect the phandles and properties that reference // other nodes. - for (auto i=n->property_begin(), e=n->property_end() ; i!=e ; ++i) + for (auto &p : n->properties()) { - for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p) + for (auto &v : *p) { - if (p->is_phandle()) + if (v.is_phandle()) { - phandles.push_back(&*p); + phandles.push_back(&v); } - if (p->is_cross_reference()) + if (v.is_cross_reference()) { - cross_references.push_back(&*p); + cross_references.push_back(&v); } } - if ((*i)->get_key() == string("phandle") || - (*i)->get_key() == string("linux,phandle")) + if (p->get_key() == string("phandle") || + p->get_key() == string("linux,phandle")) { - if ((*i)->begin()->byte_data.size() != 4) + if (p->begin()->byte_data.size() != 4) { fprintf(stderr, "Invalid phandle value for node "); n->name.dump(); @@ -1071,7 +1056,7 @@ device_tree::collect_names_recursive(nod } else { - uint32_t phandle = (*i)->begin()->get_as_uint32(); + uint32_t phandle = p->begin()->get_as_uint32(); used_phandles.insert(std::make_pair(phandle, n.get())); } } @@ -1104,12 +1089,33 @@ device_tree::resolve_cross_references() { pv->byte_data.push_back('@'); p->second.push_to_buffer(pv->byte_data); + pv->byte_data.push_back(0); } } } - uint32_t phandle = 1; + std::unordered_set phandle_set; for (auto &i : phandles) { + phandle_set.insert(i); + } + std::vector sorted_phandles; + root->visit([&](node &n) { + for (auto &p : n.properties()) + { + for (auto &v : *p) + { + if (phandle_set.count(&v)) + { + sorted_phandles.push_back(&v); + } + } + } + }); + assert(sorted_phandles.size() == phandles.size()); + + uint32_t phandle = 1; + for (auto &i : sorted_phandles) + { string target_name = i->string_data; node *target = node_names[target_name]; if (target == 0) @@ -1163,94 +1169,111 @@ device_tree::resolve_cross_references() } } -void -device_tree::parse_file(input_buffer &input, +bool +device_tree::parse_include(input_buffer &input, const std::string &dir, std::vector &roots, FILE *depfile, bool &read_header) { - input.next_token(); - // Read the header - if (input.consume("/dts-v1/;")) + if (!input.consume("/include/")) { - read_header = true; + return false; } - input.next_token(); - while(input.consume("/include/")) + bool reallyInclude = true; + if (input.consume("if ")) { - bool reallyInclude = true; - if (input.consume("if ")) - { - input.next_token(); - string name = string::parse_property_name(input); - // XXX: Error handling - if (defines.find(name) == defines.end()) - { - reallyInclude = false; - } - input.consume('/'); - } input.next_token(); - if (!input.consume('"')) + string name = string::parse_property_name(input); + // XXX: Error handling + if (defines.find(name) == defines.end()) { - input.parse_error("Expected quoted filename"); - valid = false; - return; + reallyInclude = false; } - int length = 0; - while (input[length] != '"') length++; + input.consume('/'); + } + input.next_token(); + if (!input.consume('"')) + { + input.parse_error("Expected quoted filename"); + valid = false; + return false; + } + int length = 0; + while (input[length] != '"') length++; - std::string file((const char*)input, length); - std::string include_file = dir + '/' + file; - assert(input.consume(file.c_str())); + std::string file((const char*)input, length); + std::string include_file = dir + '/' + file; + input.consume(file.c_str()); + if (!reallyInclude) + { input.consume('"'); input.next_token(); - if (!reallyInclude) - { - continue; - } + return true; + } - input_buffer *include_buffer = buffer_for_file(include_file.c_str()); + input_buffer *include_buffer = buffer_for_file(include_file.c_str(), false); - if (include_buffer == 0) + if (include_buffer == 0) + { + for (auto i : include_paths) { - for (auto i : include_paths) + include_file = i + '/' + file; + include_buffer = buffer_for_file(include_file.c_str()); + if (include_buffer != 0) { - include_file = i + '/' + file; - include_buffer = buffer_for_file(include_file.c_str()); - if (include_buffer != 0) - { - break; - } + break; } } - if (depfile != 0) - { - putc(' ', depfile); - fputs(include_file.c_str(), depfile); - } - if (include_buffer == 0) - { - valid = false; - return; - } - parse_file(*include_buffer, dir, roots, depfile, read_header); } + if (depfile != 0) + { + putc(' ', depfile); + fputs(include_file.c_str(), depfile); + } + if (include_buffer == 0) + { + input.parse_error("Unable to locate input file"); + input.consume('"'); + input.next_token(); + valid = false; + return true; + } + input.consume('"'); + input.next_token(); + parse_file(*include_buffer, dir, roots, depfile, read_header); + return true; +} + +void +device_tree::parse_file(input_buffer &input, + const std::string &dir, + std::vector &roots, + FILE *depfile, + bool &read_header) +{ + input.next_token(); + // Read the header + if (input.consume("/dts-v1/;")) + { + read_header = true; + } + input.next_token(); input.next_token(); if (!read_header) { input.parse_error("Expected /dts-v1/; version string"); } + while(parse_include(input, dir, roots, depfile, read_header)) {} // Read any memory reservations while(input.consume("/memreserve/")) { unsigned long long start, len; input.next_token(); // Read the start and length. - if (!(input.consume_integer(start) && + if (!(input.consume_integer_expression(start) && (input.next_token(), - input.consume_integer(len)))) + input.consume_integer_expression(len)))) { input.parse_error("Expected size on /memreserve/ node."); } @@ -1259,6 +1282,7 @@ device_tree::parse_file(input_buffer &in reservations.push_back(reservation(start, len)); } input.next_token(); + while(parse_include(input, dir, roots, depfile, read_header)) {} while (valid && !input.finished()) { node_ptr n; @@ -1287,11 +1311,12 @@ device_tree::parse_file(input_buffer &in valid = false; } input.next_token(); + while(parse_include(input, dir, roots, depfile, read_header)) {} } } input_buffer* -device_tree::buffer_for_file(const char *path) +device_tree::buffer_for_file(const char *path, bool warn) { if (string(path) == string("-")) { @@ -1306,7 +1331,10 @@ device_tree::buffer_for_file(const char int source = open(path, O_RDONLY); if (source == -1) { - fprintf(stderr, "Unable to open file '%s'. %s\n", path, strerror(errno)); + if (warn) + { + fprintf(stderr, "Unable to open file '%s'. %s\n", path, strerror(errno)); + } return 0; } struct stat st; @@ -1447,7 +1475,7 @@ device_tree::write_dts(int fd) } void -device_tree::parse_dtb(const char *fn, FILE *depfile) +device_tree::parse_dtb(const char *fn, FILE *) { input_buffer *in = buffer_for_file(fn); if (in == 0) Modified: head/usr.bin/dtc/fdt.hh ============================================================================== --- head/usr.bin/dtc/fdt.hh Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/fdt.hh Tue Dec 29 16:29:42 2015 (r292876) @@ -36,6 +36,7 @@ #include #include #include +#include #include "util.hh" #include "string.hh" @@ -402,11 +403,37 @@ class node * The type for the property vector. */ typedef std::vector property_vector; + /** + * Iterator type for child nodes. + */ + typedef std::vector::iterator child_iterator; private: /** + * Adaptor to use children in range-based for loops. + */ + struct child_range + { + child_range(node &nd) : n(nd) {} + child_iterator begin() { return n.child_begin(); } + child_iterator end() { return n.child_end(); } + private: + node &n; + }; + /** + * Adaptor to use properties in range-based for loops. + */ + struct property_range + { + property_range(node &nd) : n(nd) {} + property_vector::iterator begin() { return n.property_begin(); } + property_vector::iterator end() { return n.property_end(); } + private: + node &n; + }; + /** * The properties contained within this node. */ - property_vector properties; + property_vector props; /** * The children of this node. */ @@ -458,10 +485,6 @@ class node */ void sort(); /** - * Iterator type for child nodes. - */ - typedef std::vector::iterator child_iterator; - /** * Returns an iterator for the first child of this node. */ inline child_iterator child_begin() @@ -475,19 +498,27 @@ class node { return children.end(); } + inline child_range child_nodes() + { + return child_range(*this); + } + inline property_range properties() + { + return property_range(*this); + } /** * Returns an iterator after the last property of this node. */ inline property_vector::iterator property_begin() { - return properties.begin(); + return props.begin(); } /** * Returns an iterator for the first property of this node. */ inline property_vector::iterator property_end() { - return properties.end(); + return props.end(); } /** * Factory method for constructing a new node. Attempts to parse a @@ -519,7 +550,7 @@ class node */ inline void add_property(property_ptr &p) { - properties.push_back(p); + props.push_back(p); } /** * Merges a node into this one. Any properties present in both are @@ -539,6 +570,10 @@ class node * with this number of tabs. */ void write_dts(FILE *file, int indent); + /** + * Recursively visit this node and then its children. + */ + void visit(std::function); }; /** @@ -683,6 +718,14 @@ class device_tree */ void resolve_cross_references(); /** + * Parse a top-level include directive. + */ + bool parse_include(input_buffer &input, + const std::string &dir, + std::vector &roots, + FILE *depfile, + bool &read_header); + /** * Parses a dts file in the given buffer and adds the roots to the parsed * set. The `read_header` argument indicates whether the header has * already been read. Some dts files place the header in an include, @@ -698,7 +741,7 @@ class device_tree * object then keeps a reference to it, ensuring that it is not * deallocated until the device tree is destroyed. */ - input_buffer *buffer_for_file(const char *path); + input_buffer *buffer_for_file(const char *path, bool warn=true); /** * Template function that writes a dtb blob using the specified writer. * The writer defines the output format (assembly, blob). Modified: head/usr.bin/dtc/input_buffer.cc ============================================================================== --- head/usr.bin/dtc/input_buffer.cc Tue Dec 29 16:11:43 2015 (r292875) +++ head/usr.bin/dtc/input_buffer.cc Tue Dec 29 16:29:42 2015 (r292876) @@ -37,6 +37,10 @@ #include #include #include +#include +#ifndef NDEBUG +#include +#endif #include @@ -49,7 +53,6 @@ namespace dtc { - void input_buffer::skip_spaces() { @@ -131,6 +134,563 @@ input_buffer::consume_integer(unsigned l return true; } +namespace { + +/** + * Convenience typedef for the type that we use for all values. + */ +typedef unsigned long long valty; + +/** + * Expression tree currently being parsed. + */ +struct expression +{ + /** + * Evaluate this node, taking into account operator precedence. + */ + virtual valty operator()() = 0; + /** + * Returns the precedence of this node. Lower values indicate higher + * precedence. + */ + virtual int precedence() = 0; + virtual ~expression() {} +#ifndef NDEBUG + /** + * Dumps this expression to `std::cerr`, appending a newline if `nl` is + * `true`. + */ + void dump(bool nl=false) + { + if (this == nullptr) + { + std::cerr << "{nullptr}\n"; + return; + } + dump_impl(); + if (nl) + { + std::cerr << '\n'; + } + } + private: + /** + * Method that sublcasses override to implement the behaviour of `dump()`. + */ + virtual void dump_impl() = 0; +#endif +}; + +/** + * Expression wrapping a single integer. Leaf nodes in the expression tree. + */ +class terminal_expr : public expression +{ + /** + * The value that this wraps. + */ + valty val; + /** + * Evaluate. Trivially returns the value that this class wraps. + */ + valty operator()() override + { + return val; + } + int precedence() override + { + return 0; + } + public: + /** + * Constructor. + */ + terminal_expr(valty v) : val(v) {} +#ifndef NDEBUG + void dump_impl() override { std::cerr << val; } +#endif +}; + +/** + * Parenthetical expression. Exists to make the contents opaque. + */ +struct paren_expression : public expression +{ + /** + * The expression within the parentheses. + */ + expression_ptr subexpr; + /** + * Constructor. Takes the child expression as the only argument. + */ + paren_expression(expression_ptr p) : subexpr(std::move(p)) {} + int precedence() override + { + return 0; + } + /** + * Evaluate - just forwards to the underlying expression. + */ + valty operator()() override + { + return (*subexpr)(); + } +#ifndef NDEBUG + void dump_impl() override + { + std::cerr << " ("; + subexpr->dump(); + std::cerr << ") "; + } +#endif +}; + +/** + * Template class for unary operators. The `OpChar` template parameter is + * solely for debugging and makes it easy to print the expression. The `Op` + * template parameter is a function object that implements the operator that + * this class provides. Most of these are provided by the `` + * header. + */ +template +class unary_operator : public expression +{ + /** + * The subexpression for this unary operator. + */ + expression_ptr subexpr; + valty operator()() override + { + Op op; + return op((*subexpr)()); + } + /** + * All unary operators have the same precedence. They are all evaluated + * before binary expressions, but after parentheses. + */ + int precedence() override + { + return 3; + } + public: + unary_operator(expression_ptr p) : subexpr(std::move(p)) {} +#ifndef NDEBUG + void dump_impl() override + { + std::cerr << OpChar; + subexpr->dump(); + } +#endif +}; + +/** + * Abstract base class for binary operators. Allows the tree to be modified + * without knowing what the operations actually are. + */ +struct binary_operator_base : public expression +{ + /** + * The left side of the expression. + */ + expression_ptr lhs; + /** + * The right side of the expression. + */ + expression_ptr rhs; + /** + * Insert a node somewhere down the path of left children, until it would + * be preempting something that should execute first. + */ + void insert_left(binary_operator_base *new_left) + { + if (lhs->precedence() < new_left->precedence()) + { + new_left->rhs = std::move(lhs); + lhs.reset(new_left); + } + else + { + static_cast(lhs.get())->insert_left(new_left); + } + } +}; + +/** + * Template class for binary operators. The precedence and the operation are + * provided as template parameters. + */ +template +struct binary_operator : public binary_operator_base +{ + valty operator()() override + { + Op op; + return op((*lhs)(), (*rhs)()); + } + int precedence() override + { + return Precedence; + } +#ifdef NDEBUG + /** + * Constructor. Takes the name of the operator as an argument, for + * debugging. Only stores it in debug mode. + */ + binary_operator(const char *) {} +#else + const char *opName; + binary_operator(const char *o) : opName(o) {} + void dump_impl() override + { + lhs->dump(); + std::cerr << opName; + rhs->dump(); + } +#endif +}; + +/** + * Ternary conditional operators (`cond ? true : false`) are a special case - + * there are no other ternary operators. + */ +class ternary_conditional_operator : public expression +{ + /** + * The condition for the clause. + */ + expression_ptr cond; + /** + * The expression that this evaluates to if the condition is true. + */ + expression_ptr lhs; + /** + * The expression that this evaluates to if the condition is false. + */ + expression_ptr rhs; + valty operator()() override + { + return (*cond)() ? (*lhs)() : (*rhs)(); + } + int precedence() override + { + // The actual precedence of a ternary conditional operator is 15, but + // its associativity is the opposite way around to the other operators, + // so we fudge it slightly. + return 3; + } +#ifndef NDEBUG + void dump_impl() override + { + cond->dump(); + std::cerr << " ? "; + lhs->dump(); + std::cerr << " : "; + rhs->dump(); + } +#endif + public: + ternary_conditional_operator(expression_ptr c, + expression_ptr l, + expression_ptr r) : + cond(std::move(c)), lhs(std::move(l)), rhs(std::move(r)) {} +}; + +template +struct lshift +{ + constexpr T operator()(const T &lhs, const T &rhs) const + { + return lhs << rhs; + } +}; +template +struct rshift +{ + constexpr T operator()(const T &lhs, const T &rhs) const *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***