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

8 files changed, 792 insertions, 136 deletions

diff --git a/usr.bin/dtc/Makefile b/usr.bin/dtc/Makefile
index a6c722a..a834f62 100644
--- a/usr.bin/dtc/Makefile
+++ b/usr.bin/dtc/Makefile
@@ -6,7 +6,7 @@ MAN=	dtc.1
 
 WARNS?=	3
 
-CXXFLAGS+=	-std=c++11
+CXXFLAGS+=	-std=c++11 -fno-rtti -fno-exceptions
 
 NO_SHARED?=NO
 
diff --git a/usr.bin/dtc/checking.cc b/usr.bin/dtc/checking.cc
index 70731ce..26cbbe2 100644
--- a/usr.bin/dtc/checking.cc
+++ b/usr.bin/dtc/checking.cc
@@ -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_tree *tree, const node_ptr &n, property_
 }
 
 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)
diff --git a/usr.bin/dtc/checking.hh b/usr.bin/dtc/checking.hh
index 34d28c3..e3b3d45 100644
--- a/usr.bin/dtc/checking.hh
+++ b/usr.bin/dtc/checking.hh
@@ -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 <property_value::EMPTY> : public property_checker
 {
 	property_type_checker(const char* name, string property_name) : 
 		property_checker(name, property_name) {}
-	virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p)
+	virtual bool check(device_tree *, const node_ptr &, property_ptr p)
 	{
 		return p->begin() == p->end();
 	}
@@ -175,7 +175,7 @@ struct property_type_checker <property_value::STRING> : public property_checker
 {
 	property_type_checker(const char* name, string property_name) : 
 		property_checker(name, property_name) {}
-	virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p)
+	virtual bool check(device_tree *, const node_ptr &, property_ptr p)
 	{
 		return (p->begin() + 1 == p->end()) && p->begin()->is_string();
 	}
@@ -190,7 +190,7 @@ struct property_type_checker <property_value::STRING_LIST> :
 {
 	property_type_checker(const char* name, string property_name) : 
 		property_checker(name, property_name) {}
-	virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p)
+	virtual bool check(device_tree *, const node_ptr &, property_ptr p)
 	{
 		for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ;
 		     ++i)
@@ -213,7 +213,7 @@ struct property_type_checker <property_value::PHANDLE> : public property_checker
 {
 	property_type_checker(const char* name, string property_name) : 
 		property_checker(name, property_name) {}
-	virtual bool check(device_tree *tree, const node_ptr &n, property_ptr p)
+	virtual bool check(device_tree *tree, const node_ptr &, property_ptr p)
 	{
 		return (p->begin() + 1 == p->end()) && 
 			(tree->referenced_node(*p->begin()) != 0);
diff --git a/usr.bin/dtc/dtb.hh b/usr.bin/dtc/dtb.hh
index a246e96..184369b 100644
--- a/usr.bin/dtc/dtb.hh
+++ b/usr.bin/dtc/dtb.hh
@@ -186,11 +186,11 @@ class binary_writer : public output_writer
 	 *  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);
diff --git a/usr.bin/dtc/fdt.cc b/usr.bin/dtc/fdt.cc
index 3908e0e..23476ae 100644
--- a/usr.bin/dtc/fdt.cc
+++ b/usr.bin/dtc/fdt.cc
@@ -264,24 +264,6 @@ property::parse_string(input_buffer &input)
 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 &input, int cell_size)
 			//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, bool &is_property, const char *error)
 	return n;
 }
 
+void
+node::visit(std::function<void(node&)> 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_buffer &strings) : valid(true)
 					valid = false;
 					return;
 				}
-				properties.push_back(prop);
+				props.push_back(prop);
 				break;
 			}
 				break;
@@ -806,7 +791,7 @@ node::node(input_buffer &input, string n, string l, string a, define_map *define
 			}
 			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, string l, string a, define_map *define
 		}
 		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, input_buffer &strings)
 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, dtb::string_table &strings)
 	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 ; i<indent ; i++)
 	{
@@ -1039,30 +1024,30 @@ device_tree::collect_names_recursive(node_ptr &n, node_path &path)
 			fprintf(stderr, ".  References to this label will not be resolved.");
 		}
 	}
-	for (node::child_iterator i=n->child_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(node_ptr &n, node_path &path)
 			}
 			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<property_value*> phandle_set;
 	for (auto &i : phandles)
 	{
+		phandle_set.insert(i);
+	}
+	std::vector<property_value*> 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<node_ptr> &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<node_ptr> &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 &input,
 		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 &input,
 			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 *path)
 	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)
diff --git a/usr.bin/dtc/fdt.hh b/usr.bin/dtc/fdt.hh
index 7340a73..5f53f5a 100644
--- a/usr.bin/dtc/fdt.hh
+++ b/usr.bin/dtc/fdt.hh
@@ -36,6 +36,7 @@
 #include <unordered_set>
 #include <memory>
 #include <string>
+#include <functional>
 
 #include "util.hh"
 #include "string.hh"
@@ -402,11 +403,37 @@ class node
 	 * The type for the property vector.
 	 */
 	typedef std::vector<property_ptr> property_vector;
+	/**
+	 * Iterator type for child nodes.
+	 */
+	typedef std::vector<node_ptr>::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<node_ptr>::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<void(node&)>);
 };
 
 /**
@@ -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<node_ptr> &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).
diff --git a/usr.bin/dtc/input_buffer.cc b/usr.bin/dtc/input_buffer.cc
index fe8c402..6d48adc 100644
--- a/usr.bin/dtc/input_buffer.cc
+++ b/usr.bin/dtc/input_buffer.cc
@@ -37,6 +37,10 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <functional>
+#ifndef NDEBUG
+#include <iostream>
+#endif
 
 
 #include <sys/stat.h>
@@ -49,7 +53,6 @@
 
 namespace dtc
 {
-
 void
 input_buffer::skip_spaces()
 {
@@ -131,6 +134,563 @@ input_buffer::consume_integer(unsigned long long &outInt)
 	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 `<functional>`
+ * header.
+ */
+template<char OpChar, class Op>
+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<binary_operator_base*>(lhs.get())->insert_left(new_left);
+		}
+	}
+};
+
+/**
+ * Template class for binary operators.  The precedence and the operation are
+ * provided as template parameters.
+ */
+template<int Precedence, class Op>
+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<typename T>
+struct lshift
+{
+	constexpr T operator()(const T &lhs, const T &rhs) const
+	{
+		return lhs << rhs;
+	}
+};
+template<typename T>
+struct rshift
+{
+	constexpr T operator()(const T &lhs, const T &rhs) const
+	{
+		return lhs >> rhs;
+	}
+};
+template<typename T>
+struct unary_plus
+{
+	constexpr T operator()(const T &val) const
+	{
+		return +val;
+	}
+};
+// TODO: Replace with std::bit_not once we can guarantee C++14 as a baseline.
+template<typename T>
+struct bit_not
+{
+	constexpr T operator()(const T &val) const
+	{
+		return ~val;
+	}
+};
+
+} // anonymous namespace
+
+
+expression_ptr input_buffer::parse_binary_expression(expression_ptr lhs)
+{
+	next_token();
+	binary_operator_base *expr = nullptr;
+	char op = ((*this)[0]);
+	switch (op)
+	{
+		default:
+			return lhs;
+		case '+':
+			expr = new binary_operator<6, std::plus<valty>>("+");
+			break;
+		case '-':
+			expr = new binary_operator<6, std::minus<valty>>("-");
+			break;
+		case '%':
+			expr = new binary_operator<5, std::modulus<valty>>("%");
+			break;
+		case '*':
+			expr = new binary_operator<5, std::multiplies<valty>>("*");
+			break;
+		case '/':
+			expr = new binary_operator<5, std::divides<valty>>("/");
+			break;
+		case '<':
+			cursor++;
+			switch ((*this)[0])
+			{
+				default:
+					parse_error("Invalid operator");
+					return nullptr;
+				case ' ':
+				case '(':
+				case '0'...'9':
+					cursor--;
+					expr = new binary_operator<8, std::less<valty>>("<");
+					break;
+				case '=':
+					expr = new binary_operator<8, std::less_equal<valty>>("<=");
+					break;
+				case '<':
+					expr = new binary_operator<7, lshift<valty>>("<<");
+					break;
+			}
+			break;
+		case '>':
+			cursor++;
+			switch ((*this)[0])
+			{
+				default:
+					parse_error("Invalid operator");
+					return nullptr;
+				case '(':
+				case ' ':
+				case '0'...'9':
+					cursor--;
+					expr = new binary_operator<8, std::greater<valty>>(">");
+					break;
+				case '=':
+					expr = new binary_operator<8, std::greater_equal<valty>>(">=");
+					break;
+				case '>':
+					expr = new binary_operator<7, rshift<valty>>(">>");
+					break;
+					return lhs;
+			}
+			break;
+		case '=':
+			if ((*this)[1] != '=')
+			{
+				parse_error("Invalid operator");
+				return nullptr;
+			}
+			consume('=');
+			expr = new binary_operator<9, std::equal_to<valty>>("==");
+			break;
+		case '!':
+			if ((*this)[1] != '=')
+			{
+				parse_error("Invalid operator");
+				return nullptr;
+			}
+			cursor++;
+			expr = new binary_operator<9, std::not_equal_to<valty>>("!=");
+			break;
+		case '&':
+			if ((*this)[1] == '&')
+			{
+				expr = new binary_operator<13, std::logical_and<valty>>("&&");
+			}
+			else
+			{
+				expr = new binary_operator<10, std::bit_and<valty>>("&");
+			}
+			break;
+		case '|':
+			if ((*this)[1] == '|')
+			{
+				expr = new binary_operator<12, std::logical_or<valty>>("||");
+			}
+			else
+			{
+				expr = new binary_operator<14, std::bit_or<valty>>("|");
+			}
+			break;
+		case '?':
+		{
+			consume('?');
+			expression_ptr true_case = parse_expression();
+			next_token();
+			if (!true_case || !consume(':'))
+			{
+				parse_error("Expected : in ternary conditional operator");
+				return nullptr;
+			}
+			expression_ptr false_case = parse_expression();
+			if (!false_case)
+			{
+				parse_error("Expected false condition for ternary operator");
+				return nullptr;
+			}
+			return expression_ptr(new ternary_conditional_operator(std::move(lhs),
+						std::move(true_case), std::move(false_case)));
+		}
+	}
+	cursor++;
+	next_token();
+	expression_ptr e(expr);
+	expression_ptr rhs(parse_expression());
+	if (!rhs)
+	{
+		return nullptr;
+	}
+	expr->lhs = std::move(lhs);
+	if (rhs->precedence() < expr->precedence())
+	{
+		expr->rhs = std::move(rhs);
+	}
+	else
+	{
+		// If we're a normal left-to-right expression, then we need to insert
+		// this as the far-left child node of the rhs expression
+		binary_operator_base *rhs_op =
+			static_cast<binary_operator_base*>(rhs.get());
+		rhs_op->insert_left(expr);
+		e.release();
+		return rhs;
+	}
+	return e;
+}
+
+expression_ptr input_buffer::parse_expression(bool stopAtParen)
+{
+	next_token();
+	unsigned long long leftVal;
+	expression_ptr lhs;
+	switch ((*this)[0])
+	{
+		case '0'...'9':
+			if (!consume_integer(leftVal))
+			{
+				return nullptr;
+			}
+			lhs.reset(new terminal_expr(leftVal));
+			break;
+		case '(':
+		{
+			consume('(');
+			expression_ptr &&subexpr = parse_expression();
+			if (!subexpr)
+			{
+				return nullptr;
+			}
+			lhs.reset(new paren_expression(std::move(subexpr)));
+			if (!consume(')'))
+			{
+				return nullptr;
+			}
+			if (stopAtParen)
+			{
+				return lhs;
+			}
+			break;
+		}
+		case '+':
+		{
+			consume('+');
+			expression_ptr &&subexpr = parse_expression();
+			if (!subexpr)
+			{
+				return nullptr;
+			}
+			lhs.reset(new unary_operator<'+', unary_plus<valty>>(std::move(subexpr)));
+			break;
+		}
+		case '-':
+		{
+			consume('-');
+			expression_ptr &&subexpr = parse_expression();
+			if (!subexpr)
+			{
+				return nullptr;
+			}
+			lhs.reset(new unary_operator<'-', std::negate<valty>>(std::move(subexpr)));
+			break;
+		}
+		case '!':
+		{
+			consume('!');
+			expression_ptr &&subexpr = parse_expression();
+			if (!subexpr)
+			{
+				return nullptr;
+			}
+			lhs.reset(new unary_operator<'!', std::logical_not<valty>>(std::move(subexpr)));
+			break;
+		}
+		case '~':
+		{
+			consume('~');
+			expression_ptr &&subexpr = parse_expression();
+			if (!subexpr)
+			{
+				return nullptr;
+			}
+			lhs.reset(new unary_operator<'~', bit_not<valty>>(std::move(subexpr)));
+			break;
+		}
+	}
+	if (!lhs)
+	{
+		return nullptr;
+	}
+	return parse_binary_expression(std::move(lhs));
+}
+
+bool
+input_buffer::consume_integer_expression(unsigned long long &outInt)
+{
+	switch ((*this)[0])
+	{
+		case '(':
+		{
+			expression_ptr e(parse_expression(true));
+			if (!e)
+			{
+				return false;
+			}
+			outInt = (*e)();
+			return true;
+		}
+		case '0'...'9':
+			return consume_integer(outInt);
+		default:
+			return false;
+	}
+}
+
 bool
 input_buffer::consume_hex_byte(uint8_t &outByte)
 {
@@ -222,12 +782,14 @@ input_buffer::parse_error(const char *msg)
 	putc('^', stderr);
 	putc('\n', stderr);
 }
+#ifndef NDEBUG
 void
 input_buffer::dump()
 {
 	fprintf(stderr, "Current cursor: %d\n", cursor);
 	fwrite(&buffer[cursor], size-cursor, 1, stderr);
 }
+#endif
 
 mmap_input_buffer::mmap_input_buffer(int fd) : input_buffer(0, 0)
 {
diff --git a/usr.bin/dtc/input_buffer.hh b/usr.bin/dtc/input_buffer.hh
index 5b1f5d6..1a87911 100644
--- a/usr.bin/dtc/input_buffer.hh
+++ b/usr.bin/dtc/input_buffer.hh
@@ -38,6 +38,11 @@
 namespace dtc
 {
 
+namespace {
+struct expression;
+typedef std::unique_ptr<expression> expression_ptr;
+}
+
 /**
  * Class encapsulating the input file.  Can be used as a const char*, but has
  * range checking.  Attempting to access anything out of range will return a 0
@@ -62,6 +67,17 @@ class input_buffer
 	int size;
 	private:
 	/**
+	 * Parse an expression.  If `stopAtParen` is set, then only parse a number
+	 * or a parenthetical expression, otherwise assume that either is the
+	 * left-hand side of a binary expression and try to parse the right-hand
+	 * side.
+	 */
+	expression_ptr parse_expression(bool stopAtParen=false);
+	/**
+	 * Parse a binary expression, having already parsed the right-hand side.
+	 */
+	expression_ptr parse_binary_expression(expression_ptr lhs);
+	/**
 	 * The current place in the buffer where we are reading.  This class
 	 * keeps a separate size, pointer, and cursor so that we can move
 	 * forwards and backwards and still have checks that we haven't fallen
@@ -187,6 +203,11 @@ class input_buffer
 	 */
 	bool consume_integer(unsigned long long &outInt);
 	/**
+	 * Reads an arithmetic expression (containing any of the normal C
+	 * operators), evaluates it, and returns the result.
+	 */
+	bool consume_integer_expression(unsigned long long &outInt);
+	/**
 	 * Template function that consumes a binary value in big-endian format
 	 * from the input stream.  Returns true and advances the cursor if
 	 * there is a value of the correct size.  This function assumes that
@@ -233,12 +254,14 @@ class input_buffer
 	 * Prints a message indicating the location of a parse error.
 	 */
 	void parse_error(const char *msg);
+#ifndef NDEBUG
 	/**
 	 * Dumps the current cursor value and the unconsumed values in the
 	 * input buffer to the standard error.  This method is intended solely
 	 * for debugging.
 	 */
 	void dump();
+#endif
 };
 /**
  * Explicit specialisation for reading a single byte.