dt.cpp

#include <fstream>
#include <iostream>
#include <map>
#include <regex>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <locale>
#include <string.h>

#define HEAD_PRO "_____HEADER____"

using namespace std;

inline std::string str_to_lower(const std::string &str)
{
	std::locale loc;
	string s;

	for (size_t i = 0; i < str.size(); i++)
		s.push_back(std::tolower(str[i], loc));

	return s;
}

// Function to get substring from the last newline character
std::string getSubstringFromLastNewline(const std::string& input) {
	size_t lastNewlinePos = input.rfind('\n');

	if (lastNewlinePos != std::string::npos) {
		if (lastNewlinePos + 1 < input.length()) {
			return input.substr(lastNewlinePos + 1);
		} else {
			return "";
		}
	} else {
		return input;
	}
}

// Utility to trim whitespace
std::string trim(const std::string& str) {
	const char* whitespace = " \t\n\r";
	size_t start = str.find_first_not_of(whitespace);
	if (start == std::string::npos) return "";
	size_t end = str.find_last_not_of(whitespace);
	return str.substr(start, end - start + 1);
}

std::string removeComments(const std::string& code) {
	std::string result;
	bool inMultiLineComment = false;
	for (size_t i = 0; i < code.size(); ++i) {
		if (!inMultiLineComment) {
			if (i + 1 < code.size() && code[i] == '/' &&
			    code[i + 1] == '/') {
				// Skip single-line comment
				while (i < code.size() && code[i] != '\n') {
					++i;
				}
				result += '\n';	 // Keep the new line character
			} else if (i + 1 < code.size() && code[i] == '/' &&
				   code[i + 1] == '*') {
				// Enter multi-line comment
				inMultiLineComment = true;
				++i;  // Skip the '*'
			} else {
				// Copy the character if it's not a comment
				result += code[i];
			}
		} else {
			if (i + 1 < code.size() && code[i] == '*' &&
			    code[i + 1] == '/') {
				// Exit multi-line comment
				inMultiLineComment = false;
				++i;  // Skip the '/'
			}
			// Ignore characters inside multi-line comments
		}
	}
	return result;
}

// Helper function to extract the hex value if it exists
bool extractHexValue(const std::string& str, unsigned long& hexValue) {
	size_t pos = str.find_last_of('@');
	if (pos != std::string::npos && pos + 1 < str.size()) {
		std::string hexPart = str.substr(pos + 1);
		std::istringstream iss(hexPart);
		iss >> std::hex >> hexValue;
		if (!iss.fail()) {
			return true;
		}
	}
	return false;
}

std::string getAfterColon(const std::string& str) {
	std::string r = str;

	size_t pos = str.find(':');
	if (pos != std::string::npos && pos + 1 < str.size()) {
		r = trim(str.substr(pos + 1));
	}

	r = str_to_lower(r);

	//make phy-names after phys
	std::replace(r.begin(), r.end(), '-', '~');

	//treat path split '/' as '@' to make order according to actual naming.
	std::replace(r.begin(), r.end(), '/', '&');

	return r;  // If no colon, return the original string
}

// Custom comparator for the map
struct CustomCompare {
	bool operator()(const std::string& ai, const std::string& bi) const {
		std::string a = removeComments(ai);
		std::string b = removeComments(bi);
		unsigned long hexA, hexB;
		bool aHasHex = extractHexValue(a, hexA);
		bool bHasHex = extractHexValue(b, hexB);

		if (aHasHex && bHasHex) {
			if (hexA == hexB)
				return getAfterColon(a) < getAfterColon(b);

			return hexA < hexB;  // Compare by hex value if both
					     // have @hexvalue
		} else if (aHasHex) {
			return false;  // a comes before b if only a has
				       // @hexvalue
		} else if (bHasHex) {
			return true;  // b comes before a if only b has
				      // @hexvalue
		} else {
			return getAfterColon(a) < getAfterColon(b);
			// Otherwise, compare lexicographically
		}
	}
};

std::map<std::string, int> g_map;
int g_common_pri;
int g_vendor_pri;

struct CustomCompare_property : public CustomCompare {
	bool operator()(const std::string& ai, const std::string& bi) const {
		int x = g_common_pri;
		int y = x;

		if (bi.empty()) return false;

		if (ai.empty()) return true;

		if (ai.find(',') != std::string::npos) x = g_vendor_pri;
		if (bi.find(',') != std::string::npos) y = g_vendor_pri;

		if (g_map.find(ai) != g_map.end()) x = g_map[ai];
		if (g_map.find(bi) != g_map.end()) y = g_map[bi];

		if (x != y) return x < y;

		return CustomCompare::operator()(ai, bi);
	}
};

class DeviceTreeNode {
       public:
	std::string name;
	int line_num;
	std::map<std::string, std::string, CustomCompare_property> properties;
	std::map<std::string, DeviceTreeNode*, CustomCompare> children;

	DeviceTreeNode(const std::string& name, int line) : name(name), line_num(line) {}

	// Add property key-value pair
	void add_property(const std::string& key, const std::string& value) {
		properties[key] = value;
	}

	string get_string_key(const DeviceTreeNode* child)
	{
		size_t pos = child->name.find('@');
		string str = child->name.substr(0, pos);

		size_t pn = child->name.rfind('\n');
		if (pn != std::string::npos)
			str = str.substr(pn + 1);

		str += "^";
		str += to_string(child->line_num);
		if (pos < child->name.size())
			str += child->name.substr(pos);

		return str;
	}

	// Add child node
	void add_child(DeviceTreeNode* child) { children[get_string_key(child)] = child; }

	// Destructor to free children
	~DeviceTreeNode() {
		for (auto& child : children) {
			delete child.second;
		}
	}

	// Print the node and its children recursively
	void print_tree(int indent = -1) const {
		std::string indentation;
		if (indent >= 0) {
			indentation = std::string(indent, '\t');
			std::cout << indentation << name << " {\n";
		}

		for (const auto& prop : properties) {
			if (indent >= 0) {
				std::cout  << indentation << "\t" << prop.first;

				if (prop.second.length() > 0)
					std::cout << " = " << prop.second;

				std::cout << ";\n";
			} else {
				std::cout << prop.second;
			}
		}

		if (!properties.empty() && !children.empty())
			std::cout << "\n";

		int i = 0;

		for (const auto& child : children) {
			if (i)
				std::cout << "\n";
			i++;
			child.second->print_tree(indent + 1);
		}

		if (indent >= 0) std::cout << indentation << "};\n";
	}
};

std::string GetNodePath(std::vector<DeviceTreeNode*> node_stack) {
	std::string str;
	if (node_stack.size() <= 1) return str;

	for (int i = 1; i < node_stack.size(); i++) {
		str += getSubstringFromLastNewline(
		    getAfterColon(removeComments(trim(node_stack[i]->name))));
		str += '/';
	}

	return str;
}

size_t find_dt_token(const std::string &s, size_t start, const char * token)
{
	size_t i = 0;
	size_t last_cr = start;
	enum {  START_S,
		NORMAL,
		COMMENT_SINGLE,
		COMMENT_MULTI,
		COMMENT_MULTI_E, } mode = NORMAL;

	for (i = start; i < s.size(); i++) {
		char c = s[i];
		if (c == '\n')
			last_cr = i + 1;

		switch (mode) {
		case NORMAL:
			if (c == '/') mode = START_S;
			if (strchr(token, c)) return i;
			break;
		case START_S:
			mode = NORMAL;
			if (c == '/') mode = COMMENT_SINGLE;
			if (c == '*') mode = COMMENT_MULTI;
			break;
		case COMMENT_SINGLE:
			if (c == '\n') mode = NORMAL;
			break;
		case COMMENT_MULTI:
			if (c == '*') mode = COMMENT_MULTI_E;
			break;
		case COMMENT_MULTI_E:
			if (c == '/')
				mode = NORMAL;
			else
				mode = COMMENT_MULTI;
		break;
		default:
			mode = NORMAL;
			break;
		}
	}

	return i == s.size() ? std::string::npos : i;
}

class DeviceTreeParser {
       public:
	DeviceTreeNode* root;
	std::string last_key_value;
	std::map<DeviceTreeNode*, std::string> last_node_value;

	std::map<std::string, DeviceTreeNode*>
	    label_map;	// To store labeled nodes

	DeviceTreeParser() { root = new DeviceTreeNode("root", 0); }

	~DeviceTreeParser() { delete root; }

	// Parse the device tree file
	void parse(const std::string& file_path, bool warning = false) {
		std::ifstream file(file_path);
		if (!file.is_open()) {
			std::cerr << "Error: Could not open file " << file_path
				  << "\n";
			return;
		}

		std::string content((std::istreambuf_iterator<char>(file)),
				    std::istreambuf_iterator<char>());
		file.close();

		// Trim the content
		content = trim(content);

		DeviceTreeNode* current_node = root;
		std::vector<DeviceTreeNode*> node_stack = {root};

		size_t pos = find_dt_token(content, 0, "{");
		size_t old_pos = content.rfind("\n", pos);
		if (old_pos == std::string::npos)
			old_pos = 0;

		if (old_pos > 0)
			root -> add_property(HEAD_PRO, content.substr(0, old_pos - 1));

		std::string buffer;

		const char* token = "{};";

		while((pos = find_dt_token(content, old_pos, token)) < content.size()) {
			char c = content[pos];
			buffer = content.substr(old_pos, pos - old_pos);
			old_pos = pos + 1;

			if (c == '{') {
				// Start of a new node
				buffer = trim(buffer);

				DeviceTreeNode* new_node =
				    new DeviceTreeNode(buffer, pos);
				current_node->add_child(new_node);
				node_stack.push_back(new_node);

				CustomCompare compare;

				if (compare(new_node->name,
					    last_node_value[current_node]) &&
				    warning)
					std::cout << "wrong order: "
						  << GetNodePath(node_stack)
						  << "\n";

				last_node_value[current_node] = new_node->name;

				current_node = new_node;
				buffer.clear();
				last_key_value = "";
			} else if (c == '}') {
				// End of current node
				node_stack.pop_back();
				current_node = node_stack.back();
			} else if (c == ';') {
				// End of a property definition
				buffer = trim(buffer);
				if (!buffer.empty()) {
					auto key_value =
					    parse_key_value(buffer);
					if (!key_value.first.empty()) {
						current_node->add_property(
						    key_value.first,
						    key_value.second);

						CustomCompare_property compare;
						if (compare(key_value.first,
							    last_key_value) &&
						    warning)
							std::cout
							    << "wrong order: "
							    << GetNodePath(
								   node_stack)
							    << key_value.first
							    << "\n";

						last_key_value =
						    key_value.first;
					}
				}
			}
		}
	}

	void print_tree() const { root->print_tree(); }

      private:

	// Parse a key-value pair from a line like "key = value;"
	std::pair<std::string, std::string> parse_key_value (
	    const std::string& line) const {
		size_t equal_pos = find_dt_token(line, 0, "=");
		if (equal_pos == std::string::npos) return {trim(line), ""};

		std::string key = trim(line.substr(0, equal_pos));
		std::string value = trim(line.substr(equal_pos + 1));
		return {key, value};
	}
};

//first group
const char* g_order[] = {
	"compatible",
	"reg",
	"reg-names",
	"ranges",
	"regulator-name",
	"#interrupt-cells",
	"interrupt-controller",
	"interrupt-parent",
	"interrupts",
	"interrupt-names",
	"#gpio-cells",
	"gpio-controller",
	"gpio-ranges",
	"#address-cells",
	"#size-cells",
	"clocks",
	"clock-names",
	"assigned-clocks",
	"assigned-clock-parents",
	"assigned-clock-rates",
	"dmas",
	"dma-names",
};

//common property alphabet order.

//common property put after alphabet order
const char* g_order_2nd[] = {
	"gpio",
	"enable-active-high",
};

//vendor property

//"status", last one
const char* g_order_last[] = {
	"status",
};

int dt_format(std::string filename, bool check) {
	if (g_map.size() == 0) {
		int prj = 0;
		for (int j = 0; j < sizeof(g_order) / sizeof(g_order[0]); j++)
			g_map[g_order[j]] = prj++;

		g_common_pri = prj;
		prj++;
		for (int j = 0; j < sizeof(g_order_2nd) / sizeof(g_order_2nd[0]); j++)
			g_map[g_order_2nd[j]] = prj++;

		g_vendor_pri = prj;
		prj++;

		for (int j = 0; j < sizeof(g_order_last) / sizeof(g_order_last[0]); j++)
			g_map[g_order_last[j]] = prj++;

	}

	DeviceTreeParser parser;
	parser.parse(filename, check);

	if (!check) parser.print_tree();

	return 0;
}