1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qjson_p.h"
41#include <qalgorithms.h>
42
43QT_BEGIN_NAMESPACE
44
45namespace QJsonPrivate
46{
47
48static Q_CONSTEXPR Base emptyArray = { { qle_uint(sizeof(Base)) }, { 0 }, { qle_uint(0) } };
49static Q_CONSTEXPR Base emptyObject = { { qle_uint(sizeof(Base)) }, { qToLittleEndian(1u) }, { qle_uint(0) } };
50
51void Data::compact()
52{
53 Q_ASSERT(sizeof(Value) == sizeof(offset));
54
55 if (!compactionCounter)
56 return;
57
58 Base *base = header->root();
59 int reserve = 0;
60 if (base->is_object) {
61 Object *o = static_cast<Object *>(base);
62 for (int i = 0; i < (int)o->length; ++i)
63 reserve += o->entryAt(i)->usedStorage(o);
64 } else {
65 Array *a = static_cast<Array *>(base);
66 for (int i = 0; i < (int)a->length; ++i)
67 reserve += (*a)[i].usedStorage(a);
68 }
69
70 int size = sizeof(Base) + reserve + base->length*sizeof(offset);
71 int alloc = sizeof(Header) + size;
72 Header *h = (Header *) malloc(alloc);
73 Q_CHECK_PTR(h);
74 h->tag = QJsonDocument::BinaryFormatTag;
75 h->version = 1;
76 Base *b = h->root();
77 b->size = size;
78 b->is_object = header->root()->is_object;
79 b->length = base->length;
80 b->tableOffset = reserve + sizeof(Array);
81
82 int offset = sizeof(Base);
83 if (b->is_object) {
84 Object *o = static_cast<Object *>(base);
85 Object *no = static_cast<Object *>(b);
86
87 for (int i = 0; i < (int)o->length; ++i) {
88 no->table()[i] = offset;
89
90 const Entry *e = o->entryAt(i);
91 Entry *ne = no->entryAt(i);
92 int s = e->size();
93 memcpy(ne, e, s);
94 offset += s;
95 int dataSize = e->value.usedStorage(o);
96 if (dataSize) {
97 memcpy((char *)no + offset, e->value.data(o), dataSize);
98 ne->value.value = offset;
99 offset += dataSize;
100 }
101 }
102 } else {
103 Array *a = static_cast<Array *>(base);
104 Array *na = static_cast<Array *>(b);
105
106 for (int i = 0; i < (int)a->length; ++i) {
107 const Value &v = (*a)[i];
108 Value &nv = (*na)[i];
109 nv = v;
110 int dataSize = v.usedStorage(a);
111 if (dataSize) {
112 memcpy((char *)na + offset, v.data(a), dataSize);
113 nv.value = offset;
114 offset += dataSize;
115 }
116 }
117 }
118 Q_ASSERT(offset == (int)b->tableOffset);
119
120 free(header);
121 header = h;
122 this->alloc = alloc;
123 compactionCounter = 0;
124}
125
126bool Data::valid() const
127{
128 if (header->tag != QJsonDocument::BinaryFormatTag || header->version != 1u)
129 return false;
130
131 bool res = false;
132 Base *root = header->root();
133 int maxSize = alloc - sizeof(Header);
134 if (root->is_object)
135 res = static_cast<Object *>(root)->isValid(maxSize);
136 else
137 res = static_cast<Array *>(root)->isValid(maxSize);
138
139 return res;
140}
141
142
143int Base::reserveSpace(uint dataSize, int posInTable, uint numItems, bool replace)
144{
145 Q_ASSERT(posInTable >= 0 && posInTable <= (int)length);
146 if (size + dataSize >= Value::MaxSize) {
147 qWarning("QJson: Document too large to store in data structure %d %d %d", (uint)size, dataSize, Value::MaxSize);
148 return 0;
149 }
150
151 offset off = tableOffset;
152 // move table to new position
153 if (replace) {
154 memmove((char *)(table()) + dataSize, table(), length*sizeof(offset));
155 } else {
156 memmove((char *)(table() + posInTable + numItems) + dataSize, table() + posInTable, (length - posInTable)*sizeof(offset));
157 memmove((char *)(table()) + dataSize, table(), posInTable*sizeof(offset));
158 }
159 tableOffset += dataSize;
160 for (int i = 0; i < (int)numItems; ++i)
161 table()[posInTable + i] = off;
162 size += dataSize;
163 if (!replace) {
164 length += numItems;
165 size += numItems * sizeof(offset);
166 }
167 return off;
168}
169
170void Base::removeItems(int pos, int numItems)
171{
172 Q_ASSERT(pos >= 0 && pos <= (int)length);
173 if (pos + numItems < (int)length)
174 memmove(table() + pos, table() + pos + numItems, (length - pos - numItems)*sizeof(offset));
175 length -= numItems;
176}
177
178int Object::indexOf(QStringView key, bool *exists) const
179{
180 int min = 0;
181 int n = length;
182 while (n > 0) {
183 int half = n >> 1;
184 int middle = min + half;
185 if (*entryAt(middle) >= key) {
186 n = half;
187 } else {
188 min = middle + 1;
189 n -= half + 1;
190 }
191 }
192 if (min < (int)length && *entryAt(min) == key) {
193 *exists = true;
194 return min;
195 }
196 *exists = false;
197 return min;
198}
199
200int Object::indexOf(QLatin1String key, bool *exists) const
201{
202 int min = 0;
203 int n = length;
204 while (n > 0) {
205 int half = n >> 1;
206 int middle = min + half;
207 if (*entryAt(middle) >= key) {
208 n = half;
209 } else {
210 min = middle + 1;
211 n -= half + 1;
212 }
213 }
214 if (min < (int)length && *entryAt(min) == key) {
215 *exists = true;
216 return min;
217 }
218 *exists = false;
219 return min;
220}
221
222bool Object::isValid(int maxSize) const
223{
224 if (size > (uint)maxSize || tableOffset + length*sizeof(offset) > size)
225 return false;
226
227 QString lastKey;
228 for (uint i = 0; i < length; ++i) {
229 offset entryOffset = table()[i];
230 if (entryOffset + sizeof(Entry) >= tableOffset)
231 return false;
232 Entry *e = entryAt(i);
233 if (!e->isValid(tableOffset - table()[i]))
234 return false;
235 QString key = e->key();
236 if (key < lastKey)
237 return false;
238 if (!e->value.isValid(this))
239 return false;
240 lastKey = key;
241 }
242 return true;
243}
244
245
246
247bool Array::isValid(int maxSize) const
248{
249 if (size > (uint)maxSize || tableOffset + length*sizeof(offset) > size)
250 return false;
251
252 for (uint i = 0; i < length; ++i) {
253 if (!at(i).isValid(this))
254 return false;
255 }
256 return true;
257}
258
259
260bool Entry::operator ==(QStringView key) const
261{
262 if (value.latinKey)
263 return (shallowLatin1Key() == key);
264 else
265 return (shallowKey() == key);
266}
267
268bool Entry::operator==(QLatin1String key) const
269{
270 if (value.latinKey)
271 return shallowLatin1Key() == key;
272 else
273 return shallowKey() == QString(key); // ### conversion to QString
274}
275
276bool Entry::operator ==(const Entry &other) const
277{
278 if (value.latinKey) {
279 if (other.value.latinKey)
280 return shallowLatin1Key() == other.shallowLatin1Key();
281 return shallowLatin1Key() == other.shallowKey();
282 } else if (other.value.latinKey) {
283 return shallowKey() == other.shallowLatin1Key();
284 }
285 return shallowKey() == other.shallowKey();
286}
287
288bool Entry::operator >=(const Entry &other) const
289{
290 if (value.latinKey) {
291 if (other.value.latinKey)
292 return shallowLatin1Key() >= other.shallowLatin1Key();
293 return shallowLatin1Key() >= other.shallowKey();
294 } else if (other.value.latinKey) {
295 return shallowKey() >= other.shallowLatin1Key();
296 }
297 return shallowKey() >= other.shallowKey();
298}
299
300
301int Value::usedStorage(const Base *b) const
302{
303 int s = 0;
304 switch (type) {
305 case QJsonValue::Double:
306 if (latinOrIntValue)
307 break;
308 s = sizeof(double);
309 break;
310 case QJsonValue::String: {
311 char *d = data(b);
312 if (latinOrIntValue)
313 s = sizeof(ushort) + qFromLittleEndian(*(ushort *)d);
314 else
315 s = sizeof(int) + sizeof(ushort) * qFromLittleEndian(*(int *)d);
316 break;
317 }
318 case QJsonValue::Array:
319 case QJsonValue::Object:
320 s = base(b)->size;
321 break;
322 case QJsonValue::Null:
323 case QJsonValue::Bool:
324 default:
325 break;
326 }
327 return alignedSize(s);
328}
329
330inline bool isValidValueOffset(uint offset, uint tableOffset)
331{
332 return offset >= sizeof(Base)
333 && offset + sizeof(uint) <= tableOffset;
334}
335
336bool Value::isValid(const Base *b) const
337{
338 switch (type) {
339 case QJsonValue::Null:
340 case QJsonValue::Bool:
341 return true;
342 case QJsonValue::Double:
343 return latinOrIntValue || isValidValueOffset(value, b->tableOffset);
344 case QJsonValue::String:
345 if (!isValidValueOffset(value, b->tableOffset))
346 return false;
347 if (latinOrIntValue)
348 return asLatin1String(b).isValid(b->tableOffset - value);
349 return asString(b).isValid(b->tableOffset - value);
350 case QJsonValue::Array:
351 return isValidValueOffset(value, b->tableOffset)
352 && static_cast<Array *>(base(b))->isValid(b->tableOffset - value);
353 case QJsonValue::Object:
354 return isValidValueOffset(value, b->tableOffset)
355 && static_cast<Object *>(base(b))->isValid(b->tableOffset - value);
356 default:
357 return false;
358 }
359}
360
361/*!
362 \internal
363 */
364int Value::requiredStorage(QJsonValue &v, bool *compressed)
365{
366 *compressed = false;
367 switch (v.t) {
368 case QJsonValue::Double:
369 if (QJsonPrivate::compressedNumber(v.dbl) != INT_MAX) {
370 *compressed = true;
371 return 0;
372 }
373 return sizeof(double);
374 case QJsonValue::String: {
375 QString s = v.toString();
376 *compressed = QJsonPrivate::useCompressed(s);
377 return QJsonPrivate::qStringSize(s, *compressed);
378 }
379 case QJsonValue::Array:
380 case QJsonValue::Object:
381 if (v.d && v.d->compactionCounter) {
382 v.detach();
383 v.d->compact();
384 v.base = static_cast<QJsonPrivate::Base *>(v.d->header->root());
385 }
386 return v.base ? uint(v.base->size) : sizeof(QJsonPrivate::Base);
387 case QJsonValue::Undefined:
388 case QJsonValue::Null:
389 case QJsonValue::Bool:
390 break;
391 }
392 return 0;
393}
394
395/*!
396 \internal
397 */
398uint Value::valueToStore(const QJsonValue &v, uint offset)
399{
400 switch (v.t) {
401 case QJsonValue::Undefined:
402 case QJsonValue::Null:
403 break;
404 case QJsonValue::Bool:
405 return v.b;
406 case QJsonValue::Double: {
407 int c = QJsonPrivate::compressedNumber(v.dbl);
408 if (c != INT_MAX)
409 return c;
410 }
411 Q_FALLTHROUGH();
412 case QJsonValue::String:
413 case QJsonValue::Array:
414 case QJsonValue::Object:
415 return offset;
416 }
417 return 0;
418}
419
420/*!
421 \internal
422 */
423void Value::copyData(const QJsonValue &v, char *dest, bool compressed)
424{
425 switch (v.t) {
426 case QJsonValue::Double:
427 if (!compressed) {
428 qToLittleEndian(v.ui, dest);
429 }
430 break;
431 case QJsonValue::String: {
432 QString str = v.toString();
433 QJsonPrivate::copyString(dest, str, compressed);
434 break;
435 }
436 case QJsonValue::Array:
437 case QJsonValue::Object: {
438 const QJsonPrivate::Base *b = v.base;
439 if (!b)
440 b = (v.t == QJsonValue::Array ? &emptyArray : &emptyObject);
441 memcpy(dest, b, b->size);
442 break;
443 }
444 default:
445 break;
446 }
447}
448
449} // namespace QJsonPrivate
450
451QT_END_NAMESPACE
452