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

1 files changed, 563 insertions, 1 deletions

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)
 {