aboutsummaryrefslogtreecommitdiff
path: root/src/database-sqlite3.cpp
blob: 095d485c0f72523d91196fd2d8f04da5681e96d8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

/*
SQLite format specification:
	blocks:
		(PK) INT id
		BLOB data
*/


#include "database-sqlite3.h"

#include "log.h"
#include "filesys.h"
#include "exceptions.h"
#include "settings.h"
#include "porting.h"
#include "util/string.h"

#include <cassert>

// When to print messages when the database is being held locked by another process
// Note: I've seen occasional delays of over 250ms while running minetestmapper.
#define BUSY_INFO_TRESHOLD	100	// Print first informational message after 100ms.
#define BUSY_WARNING_TRESHOLD	250	// Print warning message after 250ms. Lag is increased.
#define BUSY_ERROR_TRESHOLD	1000	// Print error message after 1000ms. Significant lag.
#define BUSY_FATAL_TRESHOLD	3000	// Allow SQLITE_BUSY to be returned, which will cause a minetest crash.
#define BUSY_ERROR_INTERVAL	10000	// Safety net: report again every 10 seconds


#define SQLRES(s, r, m) \
	if ((s) != (r)) { \
		throw DatabaseException(std::string(m) + ": " +\
				sqlite3_errmsg(m_database)); \
	}
#define SQLOK(s, m) SQLRES(s, SQLITE_OK, m)

#define PREPARE_STATEMENT(name, query) \
	SQLOK(sqlite3_prepare_v2(m_database, query, -1, &m_stmt_##name, NULL),\
		"Failed to prepare query '" query "'")

#define SQLOK_ERRSTREAM(s, m)                           \
	if ((s) != SQLITE_OK) {                             \
		errorstream << (m) << ": "                      \
			<< sqlite3_errmsg(m_database) << std::endl; \
	}

#define FINALIZE_STATEMENT(statement) SQLOK_ERRSTREAM(sqlite3_finalize(statement), \
	"Failed to finalize " #statement)

int Database_SQLite3::busyHandler(void *data, int count)
{
	s64 &first_time = reinterpret_cast<s64 *>(data)[0];
	s64 &prev_time = reinterpret_cast<s64 *>(data)[1];
	s64 cur_time = getTimeMs();

	if (count == 0) {
		first_time = cur_time;
		prev_time = first_time;
	} else {
		while (cur_time < prev_time)
			cur_time += s64(1)<<32;
	}

	if (cur_time - first_time < BUSY_INFO_TRESHOLD) {
		; // do nothing
	} else if (cur_time - first_time >= BUSY_INFO_TRESHOLD &&
			prev_time - first_time < BUSY_INFO_TRESHOLD) {
		infostream << "SQLite3 database has been locked for "
			<< cur_time - first_time << " ms." << std::endl;
	} else if (cur_time - first_time >= BUSY_WARNING_TRESHOLD &&
			prev_time - first_time < BUSY_WARNING_TRESHOLD) {
		warningstream << "SQLite3 database has been locked for "
			<< cur_time - first_time << " ms." << std::endl;
	} else if (cur_time - first_time >= BUSY_ERROR_TRESHOLD &&
			prev_time - first_time < BUSY_ERROR_TRESHOLD) {
		errorstream << "SQLite3 database has been locked for "
			<< cur_time - first_time << " ms; this causes lag." << std::endl;
	} else if (cur_time - first_time >= BUSY_FATAL_TRESHOLD &&
			prev_time - first_time < BUSY_FATAL_TRESHOLD) {
		errorstream << "SQLite3 database has been locked for "
			<< cur_time - first_time << " ms - giving up!" << std::endl;
	} else if ((cur_time - first_time) / BUSY_ERROR_INTERVAL !=
			(prev_time - first_time) / BUSY_ERROR_INTERVAL) {
		// Safety net: keep reporting every BUSY_ERROR_INTERVAL
		errorstream << "SQLite3 database has been locked for "
			<< (cur_time - first_time) / 1000 << " seconds!" << std::endl;
	}

	prev_time = cur_time;

	// Make sqlite transaction fail if delay exceeds BUSY_FATAL_TRESHOLD
	return cur_time - first_time < BUSY_FATAL_TRESHOLD;
}


Database_SQLite3::Database_SQLite3(const std::string &savedir) :
	m_initialized(false),
	m_savedir(savedir),
	m_database(NULL),
	m_stmt_read(NULL),
	m_stmt_write(NULL),
	m_stmt_list(NULL),
	m_stmt_delete(NULL),
	m_stmt_begin(NULL),
	m_stmt_end(NULL)
{
}

void Database_SQLite3::beginSave() {
	verifyDatabase();
	SQLRES(sqlite3_step(m_stmt_begin), SQLITE_DONE,
		"Failed to start SQLite3 transaction");
	sqlite3_reset(m_stmt_begin);
}

void Database_SQLite3::endSave() {
	verifyDatabase();
	SQLRES(sqlite3_step(m_stmt_end), SQLITE_DONE,
		"Failed to commit SQLite3 transaction");
	sqlite3_reset(m_stmt_end);
}

void Database_SQLite3::openDatabase()
{
	if (m_database) return;

	std::string dbp = m_savedir + DIR_DELIM + "map.sqlite";

	// Open the database connection

	if (!fs::CreateAllDirs(m_savedir)) {
		infostream << "Database_SQLite3: Failed to create directory \""
			<< m_savedir << "\"" << std::endl;
		throw FileNotGoodException("Failed to create database "
				"save directory");
	}

	bool needs_create = !fs::PathExists(dbp);

	SQLOK(sqlite3_open_v2(dbp.c_str(), &m_database,
			SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE, NULL),
		std::string("Failed to open SQLite3 database file ") + dbp);

	SQLOK(sqlite3_busy_handler(m_database, Database_SQLite3::busyHandler,
		m_busy_handler_data), "Failed to set SQLite3 busy handler");

	if (needs_create) {
		createDatabase();
	}

	std::string query_str = std::string("PRAGMA synchronous = ")
			 + itos(g_settings->getU16("sqlite_synchronous"));
	SQLOK(sqlite3_exec(m_database, query_str.c_str(), NULL, NULL, NULL),
		"Failed to modify sqlite3 synchronous mode");
}

void Database_SQLite3::verifyDatabase()
{
	if (m_initialized) return;

	openDatabase();

	PREPARE_STATEMENT(begin, "BEGIN");
	PREPARE_STATEMENT(end, "COMMIT");
	PREPARE_STATEMENT(read, "SELECT `data` FROM `blocks` WHERE `pos` = ? LIMIT 1");
#ifdef __ANDROID__
	PREPARE_STATEMENT(write,  "INSERT INTO `blocks` (`pos`, `data`) VALUES (?, ?)");
#else
	PREPARE_STATEMENT(write, "REPLACE INTO `blocks` (`pos`, `data`) VALUES (?, ?)");
#endif
	PREPARE_STATEMENT(delete, "DELETE FROM `blocks` WHERE `pos` = ?");
	PREPARE_STATEMENT(list, "SELECT `pos` FROM `blocks`");

	m_initialized = true;

	verbosestream << "ServerMap: SQLite3 database opened." << std::endl;
}

inline void Database_SQLite3::bindPos(sqlite3_stmt *stmt, const v3s16 &pos, int index)
{
	SQLOK(sqlite3_bind_int64(stmt, index, getBlockAsInteger(pos)),
		"Internal error: failed to bind query at " __FILE__ ":" TOSTRING(__LINE__));
}

bool Database_SQLite3::deleteBlock(const v3s16 &pos)
{
	verifyDatabase();

	bindPos(m_stmt_delete, pos);

	bool good = sqlite3_step(m_stmt_delete) == SQLITE_DONE;
	sqlite3_reset(m_stmt_delete);

	if (!good) {
		warningstream << "deleteBlock: Block failed to delete "
			<< PP(pos) << ": " << sqlite3_errmsg(m_database) << std::endl;
	}
	return good;
}

bool Database_SQLite3::saveBlock(const v3s16 &pos, const std::string &data)
{
	verifyDatabase();

#ifdef __ANDROID__
	/**
	 * Note: For some unknown reason SQLite3 fails to REPLACE blocks on Android,
	 * deleting them and then inserting works.
	 */
	bindPos(m_stmt_read, pos);

	if (sqlite3_step(m_stmt_read) == SQLITE_ROW) {
		deleteBlock(pos);
	}
	sqlite3_reset(m_stmt_read);
#endif

	bindPos(m_stmt_write, pos);
	SQLOK(sqlite3_bind_blob(m_stmt_write, 2, data.data(), data.size(), NULL),
		"Internal error: failed to bind query at " __FILE__ ":" TOSTRING(__LINE__));

	SQLRES(sqlite3_step(m_stmt_write), SQLITE_DONE, "Failed to save block")
	sqlite3_reset(m_stmt_write);

	return true;
}

void Database_SQLite3::loadBlock(const v3s16 &pos, std::string *block)
{
	verifyDatabase();

	bindPos(m_stmt_read, pos);

	if (sqlite3_step(m_stmt_read) != SQLITE_ROW) {
		sqlite3_reset(m_stmt_read);
		return;
	}

	const char *data = (const char *) sqlite3_column_blob(m_stmt_read, 0);
	size_t len = sqlite3_column_bytes(m_stmt_read, 0);

	*block = (data) ? std::string(data, len) : "";

	sqlite3_step(m_stmt_read);
	// We should never get more than 1 row, so ok to reset
	sqlite3_reset(m_stmt_read);
}

void Database_SQLite3::createDatabase()
{
	assert(m_database); // Pre-condition
	SQLOK(sqlite3_exec(m_database,
		"CREATE TABLE IF NOT EXISTS `blocks` (\n"
		"	`pos` INT PRIMARY KEY,\n"
		"	`data` BLOB\n"
		");\n",
		NULL, NULL, NULL),
		"Failed to create database table");
}

void Database_SQLite3::listAllLoadableBlocks(std::vector<v3s16> &dst)
{
	verifyDatabase();

	while (sqlite3_step(m_stmt_list) == SQLITE_ROW) {
		dst.push_back(getIntegerAsBlock(sqlite3_column_int64(m_stmt_list, 0)));
	}
	sqlite3_reset(m_stmt_list);
}

Database_SQLite3::~Database_SQLite3()
{
	FINALIZE_STATEMENT(m_stmt_read)
	FINALIZE_STATEMENT(m_stmt_write)
	FINALIZE_STATEMENT(m_stmt_list)
	FINALIZE_STATEMENT(m_stmt_begin)
	FINALIZE_STATEMENT(m_stmt_end)
	FINALIZE_STATEMENT(m_stmt_delete)

	SQLOK_ERRSTREAM(sqlite3_close(m_database), "Failed to close database");
}

='n1262' href='#n1262'>1262 1263
/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/


#include "guiTable.h"
#include <queue>
#include <sstream>
#include <utility>
#include <cstring>
#include <IGUISkin.h>
#include <IGUIFont.h>
#include "client/renderingengine.h"
#include "debug.h"
#include "log.h"
#include "client/tile.h"
#include "gettime.h"
#include "util/string.h"
#include "util/numeric.h"
#include "util/string.h" // for parseColorString()
#include "settings.h" // for settings
#include "porting.h" // for dpi
#include "client/guiscalingfilter.h"

/*
	GUITable
*/

GUITable::GUITable(gui::IGUIEnvironment *env,
		gui::IGUIElement* parent, s32 id,
		core::rect<s32> rectangle,
		ISimpleTextureSource *tsrc
):
	gui::IGUIElement(gui::EGUIET_ELEMENT, env, parent, id, rectangle),
	m_tsrc(tsrc)
{
	assert(tsrc != NULL);

	gui::IGUISkin* skin = Environment->getSkin();

	m_font = skin->getFont();
	if (m_font) {
		m_font->grab();
		m_rowheight = m_font->getDimension(L"A").Height + 4;
		m_rowheight = MYMAX(m_rowheight, 1);
	}

	const s32 s = skin->getSize(gui::EGDS_SCROLLBAR_SIZE);
	m_scrollbar = new GUIScrollBar(Environment, this, -1,
			core::rect<s32>(RelativeRect.getWidth() - s,
					0,
					RelativeRect.getWidth(),
					RelativeRect.getHeight()),
			false, true);
	m_scrollbar->setSubElement(true);
	m_scrollbar->setTabStop(false);
	m_scrollbar->setAlignment(gui::EGUIA_LOWERRIGHT, gui::EGUIA_LOWERRIGHT,
			gui::EGUIA_UPPERLEFT, gui::EGUIA_LOWERRIGHT);
	m_scrollbar->setVisible(false);
	m_scrollbar->setPos(0);

	setTabStop(true);
	setTabOrder(-1);
	updateAbsolutePosition();
	float density = RenderingEngine::getDisplayDensity();
#ifdef __ANDROID__
	density = 1; // dp scaling is applied by the skin
#endif
	core::rect<s32> relative_rect = m_scrollbar->getRelativePosition();
	s32 width = (relative_rect.getWidth() / (2.0 / 3.0)) * density *
			g_settings->getFloat("gui_scaling");
	m_scrollbar->setRelativePosition(core::rect<s32>(
			relative_rect.LowerRightCorner.X-width,relative_rect.UpperLeftCorner.Y,
			relative_rect.LowerRightCorner.X,relative_rect.LowerRightCorner.Y
			));
}

GUITable::~GUITable()
{
	for (GUITable::Row &row : m_rows)
		delete[] row.cells;

	if (m_font)
		m_font->drop();

	if (m_scrollbar)
		m_scrollbar->drop();
}

GUITable::Option GUITable::splitOption(const std::string &str)
{
	size_t equal_pos = str.find('=');
	if (equal_pos == std::string::npos)
		return GUITable::Option(str, "");

	return GUITable::Option(str.substr(0, equal_pos),
			str.substr(equal_pos + 1));
}

void GUITable::setTextList(const std::vector<std::string> &content,
		bool transparent)
{
	clear();

	if (transparent) {
		m_background.setAlpha(0);
		m_border = false;
	}

	m_is_textlist = true;

	s32 empty_string_index = allocString("");

	m_rows.resize(content.size());
	for (s32 i = 0; i < (s32) content.size(); ++i) {
		Row *row = &m_rows[i];
		row->cells = new Cell[1];
		row->cellcount = 1;
		row->indent = 0;
		row->visible_index = i;
		m_visible_rows.push_back(i);

		Cell *cell = row->cells;
		cell->xmin = 0;
		cell->xmax = 0x7fff;  // something large enough
		cell->xpos = 6;
		cell->content_type = COLUMN_TYPE_TEXT;
		cell->content_index = empty_string_index;
		cell->tooltip_index = empty_string_index;
		cell->color.set(255, 255, 255, 255);
		cell->color_defined = false;
		cell->reported_column = 1;

		// parse row content (color)
		const std::string &s = content[i];
		if (s[0] == '#' && s[1] == '#') {
			// double # to escape
			cell->content_index = allocString(s.substr(2));
		}
		else if (s[0] == '#' && s.size() >= 7 &&
				parseColorString(
					s.substr(0,7), cell->color, false)) {
			// single # for color
			cell->color_defined = true;
			cell->content_index = allocString(s.substr(7));
		}
		else {
			// no #, just text
			cell->content_index = allocString(s);
		}

	}

	allocationComplete();

	// Clamp scroll bar position
	updateScrollBar();
}

void GUITable::setTable(const TableOptions &options,
		const TableColumns &columns,
		std::vector<std::string> &content)
{
	clear();

	// Naming conventions:
	// i is always a row index, 0-based
	// j is always a column index, 0-based
	// k is another index, for example an option index

	// Handle a stupid error case... (issue #1187)
	if (columns.empty()) {
		TableColumn text_column;
		text_column.type = "text";
		TableColumns new_columns;
		new_columns.push_back(text_column);
		setTable(options, new_columns, content);
		return;
	}

	// Handle table options
	video::SColor default_color(255, 255, 255, 255);
	s32 opendepth = 0;
	for (const Option &option : options) {
		const std::string &name = option.name;
		const std::string &value = option.value;
		if (name == "color")
			parseColorString(value, m_color, false);
		else if (name == "background")
			parseColorString(value, m_background, false);
		else if (name == "border")
			m_border = is_yes(value);
		else if (name == "highlight")
			parseColorString(value, m_highlight, false);
		else if (name == "highlight_text")
			parseColorString(value, m_highlight_text, false);
		else if (name == "opendepth")
			opendepth = stoi(value);
		else
			errorstream<<"Invalid table option: \""<<name<<"\""
				<<" (value=\""<<value<<"\")"<<std::endl;
	}

	// Get number of columns and rows
	// note: error case columns.size() == 0 was handled above
	s32 colcount = columns.size();
	assert(colcount >= 1);
	// rowcount = ceil(cellcount / colcount) but use integer arithmetic
	s32 rowcount = (content.size() + colcount - 1) / colcount;
	assert(rowcount >= 0);
	// Append empty strings to content if there is an incomplete row
	s32 cellcount = rowcount * colcount;
	while (content.size() < (u32) cellcount)
		content.emplace_back("");

	// Create temporary rows (for processing columns)
	struct TempRow {
		// Current horizontal position (may different between rows due
		// to indent/tree columns, or text/image columns with width<0)
		s32 x;
		// Tree indentation level
		s32 indent;
		// Next cell: Index into m_strings or m_images
		s32 content_index;
		// Next cell: Width in pixels
		s32 content_width;
		// Vector of completed cells in this row
		std::vector<Cell> cells;
		// Stores colors and how long they last (maximum column index)
		std::vector<std::pair<video::SColor, s32> > colors;

		TempRow(): x(0), indent(0), content_index(0), content_width(0) {}
	};
	TempRow *rows = new TempRow[rowcount];

	// Get em width. Pedantically speaking, the width of "M" is not
	// necessarily the same as the em width, but whatever, close enough.
	s32 em = 6;
	if (m_font)
		em = m_font->getDimension(L"M").Width;

	s32 default_tooltip_index = allocString("");

	std::map<s32, s32> active_image_indices;

	// Process content in column-major order
	for (s32 j = 0; j < colcount; ++j) {
		// Check column type
		ColumnType columntype = COLUMN_TYPE_TEXT;
		if (columns[j].type == "text")
			columntype = COLUMN_TYPE_TEXT;
		else if (columns[j].type == "image")
			columntype = COLUMN_TYPE_IMAGE;
		else if (columns[j].type == "color")
			columntype = COLUMN_TYPE_COLOR;
		else if (columns[j].type == "indent")
			columntype = COLUMN_TYPE_INDENT;
		else if (columns[j].type == "tree")
			columntype = COLUMN_TYPE_TREE;
		else
			errorstream<<"Invalid table column type: \""
				<<columns[j].type<<"\""<<std::endl;

		// Process column options
		s32 padding = myround(0.5 * em);
		s32 tooltip_index = default_tooltip_index;
		s32 align = 0;
		s32 width = 0;
		s32 span = colcount;

		if (columntype == COLUMN_TYPE_INDENT) {
			padding = 0; // default indent padding
		}
		if (columntype == COLUMN_TYPE_INDENT ||
				columntype == COLUMN_TYPE_TREE) {
			width = myround(em * 1.5); // default indent width
		}

		for (const Option &option : columns[j].options) {
			const std::string &name = option.name;
			const std::string &value = option.value;
			if (name == "padding")
				padding = myround(stof(value) * em);
			else if (name == "tooltip")
				tooltip_index = allocString(value);
			else if (name == "align" && value == "left")
				align = 0;
			else if (name == "align" && value == "center")
				align = 1;
			else if (name == "align" && value == "right")
				align = 2;
			else if (name == "align" && value == "inline")
				align = 3;
			else if (name == "width")
				width = myround(stof(value) * em);
			else if (name == "span" && columntype == COLUMN_TYPE_COLOR)
				span = stoi(value);
			else if (columntype == COLUMN_TYPE_IMAGE &&
					!name.empty() &&
					string_allowed(name, "0123456789")) {
				s32 content_index = allocImage(value);
				active_image_indices.insert(std::make_pair(
							stoi(name),
							content_index));
			}
			else {
				errorstream<<"Invalid table column option: \""<<name<<"\""
					<<" (value=\""<<value<<"\")"<<std::endl;
			}
		}

		// If current column type can use information from "color" columns,
		// find out which of those is currently active
		if (columntype == COLUMN_TYPE_TEXT) {
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				while (!row->colors.empty() && row->colors.back().second < j)
					row->colors.pop_back();
			}
		}

		// Make template for new cells
		Cell newcell;
		newcell.content_type = columntype;
		newcell.tooltip_index = tooltip_index;
		newcell.reported_column = j+1;

		if (columntype == COLUMN_TYPE_TEXT) {
			// Find right edge of column
			s32 xmax = 0;
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				row->content_index = allocString(content[i * colcount + j]);
				const core::stringw &text = m_strings[row->content_index];
				row->content_width = m_font ?
					m_font->getDimension(text.c_str()).Width : 0;
				row->content_width = MYMAX(row->content_width, width);
				s32 row_xmax = row->x + padding + row->content_width;
				xmax = MYMAX(xmax, row_xmax);
			}
			// Add a new cell (of text type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				newcell.xmin = rows[i].x + padding;
				alignContent(&newcell, xmax, rows[i].content_width, align);
				newcell.content_index = rows[i].content_index;
				newcell.color_defined = !rows[i].colors.empty();
				if (newcell.color_defined)
					newcell.color = rows[i].colors.back().first;
				rows[i].cells.push_back(newcell);
				rows[i].x = newcell.xmax;
			}
		}
		else if (columntype == COLUMN_TYPE_IMAGE) {
			// Find right edge of column
			s32 xmax = 0;
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				row->content_index = -1;

				// Find content_index. Image indices are defined in
				// column options so check active_image_indices.
				s32 image_index = stoi(content[i * colcount + j]);
				std::map<s32, s32>::iterator image_iter =
					active_image_indices.find(image_index);
				if (image_iter != active_image_indices.end())
					row->content_index = image_iter->second;

				// Get texture object (might be NULL)
				video::ITexture *image = NULL;
				if (row->content_index >= 0)
					image = m_images[row->content_index];

				// Get content width and update xmax
				row->content_width = image ? image->getOriginalSize().Width : 0;
				row->content_width = MYMAX(row->content_width, width);
				s32 row_xmax = row->x + padding + row->content_width;
				xmax = MYMAX(xmax, row_xmax);
			}
			// Add a new cell (of image type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				newcell.xmin = rows[i].x + padding;
				alignContent(&newcell, xmax, rows[i].content_width, align);
				newcell.content_index = rows[i].content_index;
				rows[i].cells.push_back(newcell);
				rows[i].x = newcell.xmax;
			}
			active_image_indices.clear();
		}
		else if (columntype == COLUMN_TYPE_COLOR) {
			for (s32 i = 0; i < rowcount; ++i) {
				video::SColor cellcolor(255, 255, 255, 255);
				if (parseColorString(content[i * colcount + j], cellcolor, true))
					rows[i].colors.emplace_back(cellcolor, j+span);
			}
		}
		else if (columntype == COLUMN_TYPE_INDENT ||
				columntype == COLUMN_TYPE_TREE) {
			// For column type "tree", reserve additional space for +/-
			// Also enable special processing for treeview-type tables
			s32 content_width = 0;
			if (columntype == COLUMN_TYPE_TREE) {
				content_width = m_font ? m_font->getDimension(L"+").Width : 0;
				m_has_tree_column = true;
			}
			// Add a new cell (of indent or tree type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];

				s32 indentlevel = stoi(content[i * colcount + j]);
				indentlevel = MYMAX(indentlevel, 0);
				if (columntype == COLUMN_TYPE_TREE)
					row->indent = indentlevel;

				newcell.xmin = row->x + padding;
				newcell.xpos = newcell.xmin + indentlevel * width;
				newcell.xmax = newcell.xpos + content_width;
				newcell.content_index = 0;
				newcell.color_defined = !rows[i].colors.empty();
				if (newcell.color_defined)
					newcell.color = rows[i].colors.back().first;
				row->cells.push_back(newcell);
				row->x = newcell.xmax;
			}
		}
	}

	// Copy temporary rows to not so temporary rows
	if (rowcount >= 1) {
		m_rows.resize(rowcount);
		for (s32 i = 0; i < rowcount; ++i) {
			Row *row = &m_rows[i];
			row->cellcount = rows[i].cells.size();
			row->cells = new Cell[row->cellcount];
			memcpy((void*) row->cells, (void*) &rows[i].cells[0],
					row->cellcount * sizeof(Cell));
			row->indent = rows[i].indent;
			row->visible_index = i;
			m_visible_rows.push_back(i);
		}
	}

	if (m_has_tree_column) {
		// Treeview: convert tree to indent cells on leaf rows
		for (s32 i = 0; i < rowcount; ++i) {
			if (i == rowcount-1 || m_rows[i].indent >= m_rows[i+1].indent)
				for (s32 j = 0; j < m_rows[i].cellcount; ++j)
					if (m_rows[i].cells[j].content_type == COLUMN_TYPE_TREE)
						m_rows[i].cells[j].content_type = COLUMN_TYPE_INDENT;
		}

		// Treeview: close rows according to opendepth option
		std::set<s32> opened_trees;
		for (s32 i = 0; i < rowcount; ++i)
			if (m_rows[i].indent < opendepth)
				opened_trees.insert(i);
		setOpenedTrees(opened_trees);
	}

	// Delete temporary information used only during setTable()
	delete[] rows;
	allocationComplete();

	// Clamp scroll bar position
	updateScrollBar();
}

void GUITable::clear()
{
	// Clean up cells and rows
	for (GUITable::Row &row : m_rows)
		delete[] row.cells;
	m_rows.clear();
	m_visible_rows.clear();

	// Get colors from skin
	gui::IGUISkin *skin = Environment->getSkin();
	m_color          = skin->getColor(gui::EGDC_BUTTON_TEXT);
	m_background     = skin->getColor(gui::EGDC_3D_HIGH_LIGHT);
	m_highlight      = skin->getColor(gui::EGDC_HIGH_LIGHT);
	m_highlight_text = skin->getColor(gui::EGDC_HIGH_LIGHT_TEXT);

	// Reset members
	m_is_textlist = false;
	m_has_tree_column = false;
	m_selected = -1;
	m_sel_column = 0;
	m_sel_doubleclick = false;
	m_keynav_time = 0;
	m_keynav_buffer = L"";
	m_border = true;
	m_strings.clear();
	m_images.clear();
	m_alloc_strings.clear();
	m_alloc_images.clear();
}

std::string GUITable::checkEvent()
{
	s32 sel = getSelected();
	assert(sel >= 0);

	if (sel == 0) {
		return "INV";
	}

	std::ostringstream os(std::ios::binary);
	if (m_sel_doubleclick) {
		os<<"DCL:";
		m_sel_doubleclick = false;
	}
	else {
		os<<"CHG:";
	}
	os<<sel;
	if (!m_is_textlist) {
		os<<":"<<m_sel_column;
	}
	return os.str();
}

s32 GUITable::getSelected() const
{
	if (m_selected < 0)
		return 0;

	assert(m_selected >= 0 && m_selected < (s32) m_visible_rows.size());
	return m_visible_rows[m_selected] + 1;
}

void GUITable::setSelected(s32 index)
{
	s32 old_selected = m_selected;

	m_selected = -1;
	m_sel_column = 0;
	m_sel_doubleclick = false;

	--index; // Switch from 1-based indexing to 0-based indexing

	s32 rowcount = m_rows.size();
	if (rowcount == 0 || index < 0) {
		return;
	}

	if (index >= rowcount) {
		index = rowcount - 1;
	}

	// If the selected row is not visible, open its ancestors to make it visible
	bool selection_invisible = m_rows[index].visible_index < 0;
	if (selection_invisible) {
		std::set<s32> opened_trees;
		getOpenedTrees(opened_trees);
		s32 indent = m_rows[index].indent;
		for (s32 j = index - 1; j >= 0; --j) {
			if (m_rows[j].indent < indent) {
				opened_trees.insert(j);
				indent = m_rows[j].indent;
			}
		}
		setOpenedTrees(opened_trees);
	}

	if (index >= 0) {
		m_selected = m_rows[index].visible_index;
		assert(m_selected >= 0 && m_selected < (s32) m_visible_rows.size());
	}

	if (m_selected != old_selected || selection_invisible) {
		autoScroll();
	}
}

GUITable::DynamicData GUITable::getDynamicData() const
{
	DynamicData dyndata;
	dyndata.selected = getSelected();
	dyndata.scrollpos = m_scrollbar->getPos();
	dyndata.keynav_time = m_keynav_time;
	dyndata.keynav_buffer = m_keynav_buffer;
	if (m_has_tree_column)
		getOpenedTrees(dyndata.opened_trees);
	return dyndata;
}

void GUITable::setDynamicData(const DynamicData &dyndata)
{
	if (m_has_tree_column)
		setOpenedTrees(dyndata.opened_trees);

	m_keynav_time = dyndata.keynav_time;
	m_keynav_buffer = dyndata.keynav_buffer;

	setSelected(dyndata.selected);
	m_sel_column = 0;
	m_sel_doubleclick = false;

	m_scrollbar->setPos(dyndata.scrollpos);
}

const c8* GUITable::getTypeName() const
{
	return "GUITable";
}

void GUITable::updateAbsolutePosition()
{
	IGUIElement::updateAbsolutePosition();
	updateScrollBar();
}

void GUITable::draw()
{
	if (!IsVisible)
		return;

	gui::IGUISkin *skin = Environment->getSkin();

	// draw background

	bool draw_background = m_background.getAlpha() > 0;
	if (m_border)
		skin->draw3DSunkenPane(this, m_background,
				true, draw_background,
				AbsoluteRect, &AbsoluteClippingRect);
	else if (draw_background)
		skin->draw2DRectangle(this, m_background,
				AbsoluteRect, &AbsoluteClippingRect);

	// get clipping rect

	core::rect<s32> client_clip(AbsoluteRect);
	client_clip.UpperLeftCorner.Y += 1;
	client_clip.UpperLeftCorner.X += 1;
	client_clip.LowerRightCorner.Y -= 1;
	client_clip.LowerRightCorner.X -= 1;
	if (m_scrollbar->isVisible()) {
		client_clip.LowerRightCorner.X =
				m_scrollbar->getAbsolutePosition().UpperLeftCorner.X;
	}
	client_clip.clipAgainst(AbsoluteClippingRect);

	// draw visible rows

	s32 scrollpos = m_scrollbar->getPos();
	s32 row_min = scrollpos / m_rowheight;
	s32 row_max = (scrollpos + AbsoluteRect.getHeight() - 1)
			/ m_rowheight + 1;
	row_max = MYMIN(row_max, (s32) m_visible_rows.size());

	core::rect<s32> row_rect(AbsoluteRect);
	if (m_scrollbar->isVisible())
		row_rect.LowerRightCorner.X -=
			skin->getSize(gui::EGDS_SCROLLBAR_SIZE);
	row_rect.UpperLeftCorner.Y += row_min * m_rowheight - scrollpos;
	row_rect.LowerRightCorner.Y = row_rect.UpperLeftCorner.Y + m_rowheight;

	for (s32 i = row_min; i < row_max; ++i) {
		Row *row = &m_rows[m_visible_rows[i]];
		bool is_sel = i == m_selected;
		video::SColor color = m_color;

		if (is_sel) {
			skin->draw2DRectangle(this, m_highlight, row_rect, &client_clip);
			color = m_highlight_text;
		}

		for (s32 j = 0; j < row->cellcount; ++j)
			drawCell(&row->cells[j], color, row_rect, client_clip);

		row_rect.UpperLeftCorner.Y += m_rowheight;
		row_rect.LowerRightCorner.Y += m_rowheight;
	}

	// Draw children
	IGUIElement::draw();
}

void GUITable::drawCell(const Cell *cell, video::SColor color,
		const core::rect<s32> &row_rect,
		const core::rect<s32> &client_clip)
{
	if ((cell->content_type == COLUMN_TYPE_TEXT)
			|| (cell->content_type == COLUMN_TYPE_TREE)) {

		core::rect<s32> text_rect = row_rect;
		text_rect.UpperLeftCorner.X = row_rect.UpperLeftCorner.X
				+ cell->xpos;
		text_rect.LowerRightCorner.X = row_rect.UpperLeftCorner.X
				+ cell->xmax;

		if (cell->color_defined)
			color = cell->color;

		if (m_font) {
			if (cell->content_type == COLUMN_TYPE_TEXT)
				m_font->draw(m_strings[cell->content_index],
						text_rect, color,
						false, true, &client_clip);
			else // tree
				m_font->draw(cell->content_index ? L"+" : L"-",
						text_rect, color,
						false, true, &client_clip);
		}
	}
	else if (cell->content_type == COLUMN_TYPE_IMAGE) {

		if (cell->content_index < 0)
			return;

		video::IVideoDriver *driver = Environment->getVideoDriver();
		video::ITexture *image = m_images[cell->content_index];

		if (image) {
			core::position2d<s32> dest_pos =
					row_rect.UpperLeftCorner;
			dest_pos.X += cell->xpos;
			core::rect<s32> source_rect(
					core::position2d<s32>(0, 0),
					image->getOriginalSize());
			s32 imgh = source_rect.LowerRightCorner.Y;
			s32 rowh = row_rect.getHeight();
			if (imgh < rowh)
				dest_pos.Y += (rowh - imgh) / 2;
			else
				source_rect.LowerRightCorner.Y = rowh;

			video::SColor color(255, 255, 255, 255);

			driver->draw2DImage(image, dest_pos, source_rect,
					&client_clip, color, true);
		}
	}
}

bool GUITable::OnEvent(const SEvent &event)
{
	if (!isEnabled())
		return IGUIElement::OnEvent(event);

	if (event.EventType == EET_KEY_INPUT_EVENT) {
		if (event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_DOWN ||
				event.KeyInput.Key == KEY_UP   ||
				event.KeyInput.Key == KEY_HOME ||
				event.KeyInput.Key == KEY_END  ||
				event.KeyInput.Key == KEY_NEXT ||
				event.KeyInput.Key == KEY_PRIOR)) {
			s32 offset = 0;
			switch (event.KeyInput.Key) {
				case KEY_DOWN:
					offset = 1;
					break;
				case KEY_UP:
					offset = -1;
					break;
				case KEY_HOME:
					offset = - (s32) m_visible_rows.size();
					break;
				case KEY_END:
					offset = m_visible_rows.size();
					break;
				case KEY_NEXT:
					offset = AbsoluteRect.getHeight() / m_rowheight;
					break;
				case KEY_PRIOR:
					offset = - (s32) (AbsoluteRect.getHeight() / m_rowheight);
					break;
				default:
					break;
			}
			s32 old_selected = m_selected;
			s32 rowcount = m_visible_rows.size();
			if (rowcount != 0) {
				m_selected = rangelim(m_selected + offset, 0, rowcount-1);
				autoScroll();
			}

			if (m_selected != old_selected)
				sendTableEvent(0, false);

			return true;
		}

		if (event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_LEFT ||
				event.KeyInput.Key == KEY_RIGHT)) {
			// Open/close subtree via keyboard
			if (m_selected >= 0) {
				int dir = event.KeyInput.Key == KEY_LEFT ? -1 : 1;
				toggleVisibleTree(m_selected, dir, true);
			}
			return true;
		}
		else if (!event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_RETURN ||
				event.KeyInput.Key == KEY_SPACE)) {
			sendTableEvent(0, true);
			return true;
		}
		else if (event.KeyInput.Key == KEY_ESCAPE ||
				event.KeyInput.Key == KEY_SPACE) {
			// pass to parent
		}
		else if (event.KeyInput.PressedDown && event.KeyInput.Char) {
			// change selection based on text as it is typed
			u64 now = porting::getTimeMs();
			if (now - m_keynav_time >= 500)
				m_keynav_buffer = L"";
			m_keynav_time = now;

			// add to key buffer if not a key repeat
			if (!(m_keynav_buffer.size() == 1 &&
					m_keynav_buffer[0] == event.KeyInput.Char)) {
				m_keynav_buffer.append(event.KeyInput.Char);
			}

			// find the selected item, starting at the current selection
			// don't change selection if the key buffer matches the current item
			s32 old_selected = m_selected;
			s32 start = MYMAX(m_selected, 0);
			s32 rowcount = m_visible_rows.size();
			for (s32 k = 1; k < rowcount; ++k) {
				s32 current = start + k;
				if (current >= rowcount)
					current -= rowcount;
				if (doesRowStartWith(getRow(current), m_keynav_buffer)) {
					m_selected = current;
					break;
				}
			}
			autoScroll();
			if (m_selected != old_selected)
				sendTableEvent(0, false);

			return true;
		}
	}
	if (event.EventType == EET_MOUSE_INPUT_EVENT) {
		core::position2d<s32> p(event.MouseInput.X, event.MouseInput.Y);

		if (event.MouseInput.Event == EMIE_MOUSE_WHEEL) {
			m_scrollbar->setPos(m_scrollbar->getPos() +
					(event.MouseInput.Wheel < 0 ? -3 : 3) *
					- (s32) m_rowheight / 2);
			return true;
		}

		// Find hovered row and cell
		bool really_hovering = false;
		s32 row_i = getRowAt(p.Y, really_hovering);
		const Cell *cell = NULL;
		if (really_hovering) {
			s32 cell_j = getCellAt(p.X, row_i);
			if (cell_j >= 0)
				cell = &(getRow(row_i)->cells[cell_j]);
		}

		// Update tooltip
		setToolTipText(cell ? m_strings[cell->tooltip_index].c_str() : L"");

		// Fix for #1567/#1806:
		// IGUIScrollBar passes double click events to its parent,
		// which we don't want. Detect this case and discard the event
		if (event.MouseInput.Event != EMIE_MOUSE_MOVED &&
				m_scrollbar->isVisible() &&
				m_scrollbar->isPointInside(p))
			return true;

		if (event.MouseInput.isLeftPressed() &&
				(isPointInside(p) ||
				 event.MouseInput.Event == EMIE_MOUSE_MOVED)) {
			s32 sel_column = 0;
			bool sel_doubleclick = (event.MouseInput.Event
					== EMIE_LMOUSE_DOUBLE_CLICK);
			bool plusminus_clicked = false;

			// For certain events (left click), report column
			// Also open/close subtrees when the +/- is clicked
			if (cell && (
					event.MouseInput.Event == EMIE_LMOUSE_PRESSED_DOWN ||
					event.MouseInput.Event == EMIE_LMOUSE_DOUBLE_CLICK ||
					event.MouseInput.Event == EMIE_LMOUSE_TRIPLE_CLICK)) {
				sel_column = cell->reported_column;
				if (cell->content_type == COLUMN_TYPE_TREE)
					plusminus_clicked = true;
			}

			if (plusminus_clicked) {
				if (event.MouseInput.Event == EMIE_LMOUSE_PRESSED_DOWN) {
					toggleVisibleTree(row_i, 0, false);
				}
			}
			else {
				// Normal selection
				s32 old_selected = m_selected;
				m_selected = row_i;
				autoScroll();

				if (m_selected != old_selected ||
						sel_column >= 1 ||
						sel_doubleclick) {
					sendTableEvent(sel_column, sel_doubleclick);
				}

				// Treeview: double click opens/closes trees
				if (m_has_tree_column && sel_doubleclick) {
					toggleVisibleTree(m_selected, 0, false);
				}
			}
		}
		return true;
	}
	if (event.EventType == EET_GUI_EVENT &&
			event.GUIEvent.EventType == gui::EGET_SCROLL_BAR_CHANGED &&
			event.GUIEvent.Caller == m_scrollbar) {
		// Don't pass events from our scrollbar to the parent
		return true;
	}

	return IGUIElement::OnEvent(event);
}

/******************************************************************************/
/* GUITable helper functions                                                  */
/******************************************************************************/

s32 GUITable::allocString(const std::string &text)
{
	std::map<std::string, s32>::iterator it = m_alloc_strings.find(text);
	if (it == m_alloc_strings.end()) {
		s32 id = m_strings.size();
		std::wstring wtext = utf8_to_wide(text);
		m_strings.emplace_back(wtext.c_str());
		m_alloc_strings.insert(std::make_pair(text, id));
		return id;
	}

	return it->second;
}

s32 GUITable::allocImage(const std::string &imagename)
{
	std::map<std::string, s32>::iterator it = m_alloc_images.find(imagename);
	if (it == m_alloc_images.end()) {
		s32 id = m_images.size();
		m_images.push_back(m_tsrc->getTexture(imagename));
		m_alloc_images.insert(std::make_pair(imagename, id));
		return id;
	}

	return it->second;
}

void GUITable::allocationComplete()
{
	// Called when done with creating rows and cells from table data,
	// i.e. when allocString and allocImage won't be called anymore
	m_alloc_strings.clear();
	m_alloc_images.clear();
}

const GUITable::Row* GUITable::getRow(s32 i) const
{
	if (i >= 0 && i < (s32) m_visible_rows.size())
		return &m_rows[m_visible_rows[i]];

	return NULL;
}

bool GUITable::doesRowStartWith(const Row *row, const core::stringw &str) const
{
	if (row == NULL)
		return false;

	for (s32 j = 0; j < row->cellcount; ++j) {
		Cell *cell = &row->cells[j];
		if (cell->content_type == COLUMN_TYPE_TEXT) {
			const core::stringw &cellstr = m_strings[cell->content_index];
			if (cellstr.size() >= str.size() &&
					str.equals_ignore_case(cellstr.subString(0, str.size())))
				return true;
		}
	}
	return false;
}

s32 GUITable::getRowAt(s32 y, bool &really_hovering) const
{
	really_hovering = false;

	s32 rowcount = m_visible_rows.size();
	if (rowcount == 0)
		return -1;

	// Use arithmetic to find row
	s32 rel_y = y - AbsoluteRect.UpperLeftCorner.Y - 1;
	s32 i = (rel_y + m_scrollbar->getPos()) / m_rowheight;

	if (i >= 0 && i < rowcount) {
		really_hovering = true;
		return i;
	}
	if (i < 0)
		return 0;

	return rowcount - 1;
}

s32 GUITable::getCellAt(s32 x, s32 row_i) const
{
	const Row *row = getRow(row_i);
	if (row == NULL)
		return -1;

	// Use binary search to find cell in row
	s32 rel_x = x - AbsoluteRect.UpperLeftCorner.X - 1;
	s32 jmin = 0;
	s32 jmax = row->cellcount - 1;
	while (jmin < jmax) {
		s32 pivot = jmin + (jmax - jmin) / 2;
		assert(pivot >= 0 && pivot < row->cellcount);
		const Cell *cell = &row->cells[pivot];

		if (rel_x >= cell->xmin && rel_x <= cell->xmax)
			return pivot;

		if (rel_x < cell->xmin)
			jmax = pivot - 1;
		else
			jmin = pivot + 1;
	}

	if (jmin >= 0 && jmin < row->cellcount &&
			rel_x >= row->cells[jmin].xmin &&
			rel_x <= row->cells[jmin].xmax)
		return jmin;

	return -1;
}

void GUITable::autoScroll()
{
	if (m_selected >= 0) {
		s32 pos = m_scrollbar->getPos();
		s32 maxpos = m_selected * m_rowheight;
		s32 minpos = maxpos - (AbsoluteRect.getHeight() - m_rowheight);
		if (pos > maxpos)
			m_scrollbar->setPos(maxpos);
		else if (pos < minpos)
			m_scrollbar->setPos(minpos);
	}
}

void GUITable::updateScrollBar()
{
	s32 totalheight = m_rowheight * m_visible_rows.size();
	s32 scrollmax = MYMAX(0, totalheight - AbsoluteRect.getHeight());
	m_scrollbar->setVisible(scrollmax > 0);
	m_scrollbar->setMax(scrollmax);
	m_scrollbar->setSmallStep(m_rowheight);
	m_scrollbar->setLargeStep(2 * m_rowheight);
	m_scrollbar->setPageSize(totalheight);
}

void GUITable::sendTableEvent(s32 column, bool doubleclick)
{
	m_sel_column = column;
	m_sel_doubleclick = doubleclick;
	if (Parent) {
		SEvent e;
		memset(&e, 0, sizeof e);
		e.EventType = EET_GUI_EVENT;
		e.GUIEvent.Caller = this;
		e.GUIEvent.Element = 0;
		e.GUIEvent.EventType = gui::EGET_TABLE_CHANGED;
		Parent->OnEvent(e);
	}
}

void GUITable::getOpenedTrees(std::set<s32> &opened_trees) const
{
	opened_trees.clear();
	s32 rowcount = m_rows.size();
	for (s32 i = 0; i < rowcount - 1; ++i) {
		if (m_rows[i].indent < m_rows[i+1].indent &&
				m_rows[i+1].visible_index != -2)
			opened_trees.insert(i);
	}
}

void GUITable::setOpenedTrees(const std::set<s32> &opened_trees)
{
	s32 old_selected = -1;
	if (m_selected >= 0)
		old_selected = m_visible_rows[m_selected];

	std::vector<s32> parents;
	std::vector<s32> closed_parents;

	m_visible_rows.clear();

	for (size_t i = 0; i < m_rows.size(); ++i) {
		Row *row = &m_rows[i];

		// Update list of ancestors
		while (!parents.empty() && m_rows[parents.back()].indent >= row->indent)
			parents.pop_back();
		while (!closed_parents.empty() &&
				m_rows[closed_parents.back()].indent >= row->indent)
			closed_parents.pop_back();

		assert(closed_parents.size() <= parents.size());

		if (closed_parents.empty()) {
			// Visible row
			row->visible_index = m_visible_rows.size();
			m_visible_rows.push_back(i);
		}
		else if (parents.back() == closed_parents.back()) {
			// Invisible row, direct parent is closed
			row->visible_index = -2;
		}
		else {
			// Invisible row, direct parent is open, some ancestor is closed
			row->visible_index = -1;
		}

		// If not a leaf, add to parents list
		if (i < m_rows.size()-1 && row->indent < m_rows[i+1].indent) {
			parents.push_back(i);