cbits/hexml.c · typeable/hexml

git.iko.soy/typeable/hexml

on master help sign in

typeable/hexml/cbits/hexml.c

551 lines 15 kB history raw

1#include "hexml.h"

2#include <stdlib.h>

3#include <string.h>

4#include <assert.h>

5#include <ctype.h>

6#include <stdio.h>

8typedef int bool;

10/////////////////////////////////////////////////////////////////////

11// TYPES

13static inline int end(str s) { return s.start + s.length; }

15static inline str start_length(int32_t start, int32_t length)

16{

17 assert(start >= 0 && length >= 0);

18 str res;

19 res.start = start;

20 res.length = length;

21 return res;

22}

24static inline str start_end(int32_t start, int32_t end)

25{

26 return start_length(start, end - start);

27}

29typedef struct

30{

31 int size;

32 int used;

33 attr* attrs; // dynamically allocated buffer

34 attr* alloc; // what to call free on

35} attr_buffer;

37typedef struct

38{

39 // have a cursor at the front, which is all the stuff I have written out, final

40 // have a cursor at the end, which is stack scoped, so children write out, then I do

41 // when you commit, you copy over from end to front

43 // nodes

44 int size;

45 int used_front; // front entries, stored for good

46 int used_back; // back entries, stack based, copied into front

47 node* nodes; // dynamically allocated buffer

48 node* alloc; // what to call free on

49} node_buffer;

52struct document

53{

54 const char* body; // pointer to initial argument, not owned by us

56 // things only used while parsing

57 const char* cursor; // pointer to where we are in body

58 const char* end; // pointer to one past the last char

59 // if cursor is > end we have gone past the end

61 char* error_message;

62 node_buffer nodes;

63 attr_buffer attrs;

64};

66static inline int doc_length(const document* d) { return (int) (d->end - d->body); }

67static inline int doc_position(const document* d) { return (int) (d->cursor - d->body); }

70/////////////////////////////////////////////////////////////////////

71// RENDER CODE

73typedef struct

74{

75 const document* d;

76 char* buffer;

77 int length;

78 int cursor;

79} render;

81static inline void render_char(render* r, char c)

82{

83 if (r->cursor < r->length)

84 r->buffer[r->cursor] = c;

85 r->cursor++;

86}

88static inline void bound(int idx, int mn, int mx)

89{

90 assert(idx >= mn && idx <= mx);

91}

93static inline void bound_str(str s, int mn, int mx)

94{

95 assert(s.length >= 0);

96 bound(s.start, mn, mx);

97 bound(end(s), mn, mx);

98}

100static void render_str(render* r, str s)

101{

102 bound_str(s, 0, doc_length(r->d));

103 for (int i = 0; i < s.length; i++)

104 render_char(r, r->d->body[s.start + i]);

105}

106

107static void render_tag(render* r, const node* n);

108

109static void render_content(render* r, const node* n)

110{

111 bound_str(n->inner, 0, doc_length(r->d));

112 bound_str(n->nodes, 0, r->d->nodes.used_front);

113 bound_str(n->attrs, 0, r->d->attrs.used);

114

115 int done = n->inner.start;

116 for (int i = 0; i < n->nodes.length; i++)

117 {

118 node* x = &r->d->nodes.nodes[n->nodes.start + i];

119 render_str(r, start_end(done, x->outer.start));

120 done = end(x->outer);

121 render_tag(r, x);

122 }

123 render_str(r, start_end(done, end(n->inner)));

124}

125

126static void render_tag(render* r, const node* n)

127{

128 render_char(r, '<');

129 render_str(r, n->name);

130 for (int i = 0; i < n->attrs.length; i++)

131 {

132 attr* x = &r->d->attrs.attrs[n->attrs.start + i];

133 render_char(r, ' ');

134 render_str(r, x->name);

135 render_char(r, '=');

136 render_char(r, '\"');

137 render_str(r, x->value);

138 render_char(r, '\"');

139 }

140 render_char(r, '>');

141 render_content(r, n);

142 render_char(r, '<');

143 render_char(r, '/');

144 render_str(r, n->name);

145 render_char(r, '>');

146}

147

148int hexml_node_render(const document* d, const node* n, char* buffer, int length)

149{

150 render r;

151 r.d = d;

152 r.buffer = buffer;

153 r.length = length;

154 r.cursor = 0;

155 // The root node (and only the root node) has an empty length, so just render its innards

156 if (n->name.length == 0)

157 render_content(&r, n);

158 else

159 render_tag(&r, n);

160 return r.cursor;

161}

162

163

164/////////////////////////////////////////////////////////////////////

165// NOT THE PARSER

166

167char* hexml_document_error(const document* d){return d->error_message;}

168node* hexml_document_node(const document* d){return &d->nodes.nodes[0];}

169

170void hexml_document_free(document* d)

171{

172 free(d->error_message);

173 free(d->nodes.alloc);

174 free(d->attrs.alloc);

175 free(d);

176}

177

178node* hexml_node_children(const document* d, const node* n, int* res)

179{

180 *res = n->nodes.length;

181 return &d->nodes.nodes[n->nodes.start];

182}

183

184attr* hexml_node_attributes(const document* d, const node* n, int* res)

185{

186 *res = n->attrs.length;

187 return &d->attrs.attrs[n->attrs.start];

188}

189

190

191attr* hexml_node_attribute(const document* d, const node* n, const char* s, int slen)

192{

193 if (slen == -1) slen = (int) strlen(s);

194 const int limit = end(n->attrs);

195 for (int i = n->attrs.start; i < limit; i++)

196 {

197 attr* r = &d->attrs.attrs[i];

198 if (r->name.length == slen && memcmp(s, &d->body[r->name.start], slen) == 0)

199 return r;

200 }

201 return NULL;

202}

203

204// Search for given strings within a node

205node* hexml_node_child(const document* d, const node* parent, const node* prev, const char* s, int slen)

206{

207 if (slen == -1) slen = (int) strlen(s);

208 int i = prev == NULL ? parent->nodes.start : (int) (prev + 1 - d->nodes.nodes);

209 const int limit = end(parent->nodes);

210 for (; i < limit; i++)

211 {

212 node* r = &d->nodes.nodes[i];

213 if (r->name.length == slen && memcmp(s, &d->body[r->name.start], slen) == 0)

214 return r;

215 }

216 return NULL;

217}

218

219

220/////////////////////////////////////////////////////////////////////

221// PARSE TABLE

222

223static const char tag_name1 = 0x1;

224static const char tag_name = 0x2;

225static const char tag_space = 0x4;

226

227static char parse_table[256];

228

229static void init_parse_table()

230{

231 static bool done = 0;

232 if (done) return;

233 for (int i = 0; i < 256; i++)

234 {

235 bool name1 = i == ':' || i == '_' || (i >= 'a' && i <= 'z') || (i >= 'A' && i <= 'Z');

236 bool name = name1 || i == '-' || i == '.' || (i >= '0' && i <= '9');

237 bool space = i == ' ' || i == '\t' || i == '\r' || i == '\n';

238 parse_table[i] = (name1 ? tag_name1 : 0) | (name ? tag_name : 0) | (space ? tag_space : 0);

239 }

240 done = 1;

241}

242

243static inline bool is(char c, char tag) { return parse_table[(unsigned char) c] & tag; }

244static inline bool is_name1(char c) { return is(c, tag_name1); }

245static inline bool is_name(char c) { return is(c, tag_name); }

246static inline bool is_space(char c) { return is(c, tag_space); }

247

248

249/////////////////////////////////////////////////////////////////////

250// PARSER COMBINATORS

251

252static inline char peek_at(const document* d, int i) { return d->cursor[i]; }

253static inline char peek(const document* d) { return peek_at(d, 0); }

254static inline void skip(document* d, int i) { d->cursor += i; }

255static inline char get(document* d) { char c = peek(d); skip(d, 1); return c; }

256

257// Remove whitespace characters from the cursor while they are still whitespace

258static inline void trim(document* d)

259{

260 while (is_space(peek(d)))

261 skip(d, 1);

262}

263

264// Find this character form the cursor onwards, if true adjust the cursor to that char, otherwise leave it at the end

265static bool find(document* d, char c)

266{

267 char* x = memchr(d->cursor, c, d->end - d->cursor);

268 if (x == NULL)

269 {

270 d->cursor = d->end;

271 return 0;

272 }

273 else

274 {

275 d->cursor = x;

276 return 1;

277 }

278}

279

280

281/////////////////////////////////////////////////////////////////////

282// PARSING CODE

283

284static inline void node_alloc(node_buffer* b, int ask)

285{

286 int space = b->size - b->used_back - b->used_front;

287 if (space >= ask) return;

288 int size2 = (b->size + 1000 + ask) * 2;

289 node* buf2 = malloc(size2 * sizeof(node));

290 assert(buf2);

291 memcpy(buf2, b->nodes, b->used_front * sizeof(node));

292 memcpy(&buf2[size2 - b->used_back], &b->nodes[b->size - b->used_back], b->used_back * sizeof(node));

293 free(b->alloc);

294 b->size = size2;

295 b->nodes = buf2;

296 b->alloc = buf2;

297}

298

299static inline void attr_alloc(attr_buffer* b, int ask)

300{

301 int space = b->size - b->used;

302 if (space >= ask) return;

303 int size2 = (b->size + 1000 + ask) * 2;

304 attr* buf2 = malloc(size2 * sizeof(attr));

305 assert(buf2);

306 memcpy(buf2, b->attrs, b->used * sizeof(attr));

307 free(b->alloc);

308 b->size = size2;

309 b->attrs = buf2;

310 b->alloc = buf2;

311}

312

313static void set_error(document* d, const char* msg)

314{

315 if (d->error_message != NULL) return; // keep the first error message

316 d->error_message = malloc(strlen(msg)+1);

317 assert(d->error_message);

318 strcpy(d->error_message, msg);

319}

320

321// you now expect a name, perhaps preceeded by whitespace

322// the name may be empty

323static inline str parse_name(document* d)

324{

325 int start = doc_position(d);

326 if (!is_name1(peek(d)))

327 return start_length(start, 0);

328 skip(d, 1);

329 while (is_name(peek(d)))

330 skip(d, 1);

331 return start_end(start, doc_position(d));

332}

333

334static inline str parse_attrval(document* d)

335{

336 trim(d);

337 if (peek(d) != '=')

338 {

339 set_error(d, "Expected = in attribute, but missing");

340 return start_length(0, 0);

341 }

342 skip(d, 1);

343 trim(d);

344 char c = peek(d);

345 if (c == '\"' || c == '\'')

346 {

347 skip(d, 1);

348 int start = doc_position(d);

349 if (!find(d, c))

350 {

351 set_error(d, "Couldn't find closing attribute bit");

352 return start_length(0, 0);

353 }

354 skip(d, 1);

355 return start_end(start, doc_position(d) - 1);

356 }

357 else

358 {

359 set_error(d, "Invalid attribute");

360 return start_length(0, 0);

361 }

362}

363

364

365

366// seen a tag name, now looking for attributes terminated by >

367// puts the attributes it finds in the attribute buffer

368static inline str parse_attributes(document* d)

369{

370 int start = d->attrs.used;

371 while (d->error_message == NULL)

372 {

373 trim(d);

374 str name = parse_name(d);

375 if (name.length == 0) break;

376 attr_alloc(&d->attrs, 1);

377 d->attrs.attrs[d->attrs.used].name = name;

378 d->attrs.attrs[d->attrs.used].value = parse_attrval(d);

379 d->attrs.used++;

380 }

381 return start_end(start, d->attrs.used);

382}

383

384static str parse_content(document* d);

385

386

387// Add a new entry into tag, am at a '<'

388static inline void parse_tag(document* d)

389{

390 node_alloc(&d->nodes, 1);

391 d->nodes.used_back++;

392 node* me = &d->nodes.nodes[d->nodes.size - d->nodes.used_back];

393

394 me->outer.start = doc_position(d);

395 char c = get(d);

396 assert(c == '<');

397 if (peek(d) == '?') skip(d, 1);

398 me->name = parse_name(d);

399 if (me->name.length == 0)

400 {

401 set_error(d, "Missing tag name");

402 return;

403 }

404 me->attrs = parse_attributes(d);

405 if (d->error_message != NULL) return;

406

407 c = peek(d);

408 if ((c == '/' || c == '?') && peek_at(d, 1) == '>')

409 {

410 skip(d, 2);

411 me->nodes = start_length(0, 0);

412 me->outer.length = start_end(me->outer.start, doc_position(d)).length;

413 me->inner = start_length(doc_position(d), 0);

414 return;

415 }

416 else if (c != '>')

417 {

418 set_error(d, "Gunk at the end of the tag");

419 return;

420 }

421 else

422 skip(d, 1);

423 me->inner.start = doc_position(d);

424 str content = parse_content(d);

425

426 // parse_content may have allocated more nodes, so recompute me

427 me = &d->nodes.nodes[d->nodes.size - d->nodes.used_back];

428 me->nodes = content;

429 me->inner.length = start_end(me->inner.start, doc_position(d)).length;

430

431 if (d->error_message != NULL) return;

432 if (peek(d) == '<' && peek_at(d, 1) == '/')

433 {

434 skip(d, 2);

435 if (d->end - d->cursor >= me->name.length &&

436 memcmp(d->cursor, &d->body[me->name.start], me->name.length) == 0)

437 {

438 skip(d, me->name.length);

439 trim(d);

440 if (get(d) == '>')

441 {

442 me->outer.length = start_end(me->outer.start, doc_position(d)).length;

443 return;

444 }

445 }

446 set_error(d, "Mismatch in closing tags");

447 return;

448 }

449 set_error(d, "Weirdness when trying to close tags");

450}

451

452// Parser until </, return the index of your node children

453// Not inline as it is recursive

454static str parse_content(document* d)

455{

456 int before = d->nodes.used_back;

457 while (d->error_message == NULL)

458 {

459 // only < can have any impact

460 if (!find(d, '<'))

461 {

462 break;

463 }

464 else if (peek_at(d, 1) == '/')

465 {

466 // have found a </

467 break;

468 }

469 else if (peek_at(d, 1) == '!' && peek_at(d, 2) == '-' && peek_at(d, 3) == '-')

470 {

471 skip(d, 3);

472 // you can't reuse the two '-' characters for the closing as well

473 if (peek_at(d, 0) == '\0' || peek_at(d, 1) == '\0')

474 {

475 set_error(d, "Didn't get a closing comment");

476 return start_end(0, 0);

477 }

478 skip(d, 2);

479 for (;;)

480 {

481 if (!find(d, '>'))

482 {

483 set_error(d, "Didn't get a closing comment");

484 return start_end(0, 0);

485 }

486 skip(d, 1);

487 if (peek_at(d, -3) == '-' && peek_at(d, -2) == '-')

488 break;

489 }

490 }

491 else

492 {

493 parse_tag(d);

494 }

495 }

496 int diff = d->nodes.used_back - before;

497 node_alloc(&d->nodes, diff);

498 str res = start_length(d->nodes.used_front, diff);

499 for (int i = 0; i < diff; i++)

500 d->nodes.nodes[d->nodes.used_front + i] = d->nodes.nodes[d->nodes.size - d->nodes.used_back + diff - 1 - i];

501 d->nodes.used_front += diff;

502 d->nodes.used_back -= diff;

503 return res;

504}

505

506// Based on looking at ~50Kb XML documents, they seem to have ~700 attributes

507// and ~300 nodes, so size appropriately to cope with that.

508typedef struct

509{

510 document document;

511 attr attrs[1000];

512 node nodes[500];

513} buffer;

514

515document* hexml_document_parse(const char* s, int slen)

516{

517 if (slen == -1) slen = (int) strlen(s);

518 assert(s[slen] == 0);

519 init_parse_table();

520

521 buffer* buf = malloc(sizeof(buffer));

522 assert(buf);

523 document* d = &buf->document;

524 d->body = s;

525 d->cursor = s;

526 d->end = &s[slen];

527 d->error_message = NULL;

528 d->attrs.size = 1000;

529 d->attrs.used = 0;

530 d->attrs.attrs = buf->attrs;

531 d->attrs.alloc = NULL;

532 d->nodes.size = 500;

533 d->nodes.used_back = 0;

534 d->nodes.used_front = 1;

535 d->nodes.nodes = buf->nodes;

536 d->nodes.alloc = NULL;

537

538 d->nodes.nodes[0].name = start_length(0, 0);

539 d->nodes.nodes[0].outer = start_length(0, slen);

540 d->nodes.nodes[0].inner = start_length(0, slen);

541 d->nodes.nodes[0].attrs = start_length(0, 0);

542

543 // Introduce an intermediate result, otherwise behaviour is undefined

544 // because there is no guaranteed ordering between LHS and RHS evaluation

545 str content = parse_content(d);

546 d->nodes.nodes[0].nodes = content;

547

548 if (d->cursor < d->end)

549 set_error(d, "Trailing junk at the end of the document");

550 return d;

551}