xml-tree.cpp

   1 extern "C" {
   2 #include <unistd.h>
   3 #include <sys/types.h>
   4 #include <sys/stat.h>
   5 #include <fcntl.h>
   6 }
   7
   8 #include <stdexcept>
   9 #include <cerrno>
  10 #include <cstring>
  11 #include <cstdio>
  12 #include "xml-tree.hpp"
  13
  14 using namespace SXSI;
  15
  16 const xml_tree::node_t xml_tree::NIL;
  17 const xml_tree::node_t xml_tree::ROOT;
  18
  19
  20 const xml_tree::tag_t xml_tree::NIL_TAG_ID;
  21 const char* xml_tree::NIL_TAG = "<!NIL!>";
  22 const xml_tree::tag_t xml_tree::DOCUMENT_OPEN_TAG_ID;
  23 const char* xml_tree::DOCUMENT_OPEN_TAG = "";
  24 const xml_tree::tag_t xml_tree::ATTRIBUTE_OPEN_TAG_ID;
  25 const char* xml_tree::ATTRIBUTE_OPEN_TAG = "<@>";
  26 const xml_tree::tag_t xml_tree::PCDATA_OPEN_TAG_ID;
  27 const char* xml_tree::PCDATA_OPEN_TAG = "<$>";
  28 const xml_tree::tag_t xml_tree::ATTRIBUTE_DATA_OPEN_TAG_ID;
  29 const char* xml_tree::ATTRIBUTE_DATA_OPEN_TAG = "<@$>";
  30 const xml_tree::tag_t xml_tree::CLOSE_TAG_ID;
  31 const char* xml_tree::CLOSE_TAG = "</>";
  32
  33
  34 static int bits8 (int t ) {
  35   int r = bits(t);
  36   if (r <= 8)
  37     return 8;
  38   else if (r <= 16)
  39     return 16;
  40   else
  41     return r;
  42 }
  43
  44
  45 static bool array_mem(xml_tree::tag_t *a, xml_tree::tag_t t)
  46 {
  47   for(; *a != xml_tree::NIL_TAG_ID; a++){
  48     if (*a >= t) return (*a == t);
  49   };
  50   return false;
  51 }
  52
  53 static void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream)
  54  {
  55     size_t res;
  56     res = fread(ptr,size,nmemb,stream);
  57     if (res < nmemb)
  58       throw std::runtime_error("ufread I/O error" );
  59     return;
  60  }
  61
  62 static void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream)
  63  {
  64     size_t res;
  65     res = fwrite(ptr,size,nmemb,stream);
  66     if (res < nmemb)
  67       throw std::runtime_error("ufwrite I/O error");
  68     return;
  69  }
  70
  71
  72
  73 xml_tree::xml_tree()
  74 {
  75   print_stack = 0;
  76   print_buffer = 0;
  77 }
  78
  79 xml_tree::xml_tree(std::vector<int32_t> *tags,
  80                    std::unordered_map<std::string, int32_t> *tag_ids,
  81                    bit_vector *parbitmap,
  82                    bool disable_tc,
  83                    SXSI::TextCollectionBuilder *tc_builder,
  84                    SXSI::TextCollectionBuilder::index_type_t idx_type,
  85                    bit_vector *textbitmap)
  86 {
  87   print_stack = 0;
  88   print_buffer = 0;
  89
  90   size_t npar = parbitmap->size();
  91   parbitmap->pack();
  92
  93   par = bp_construct(npar,
  94                      parbitmap->get_vector_ptr(),
  95                      OPT_DEGREE);
  96   delete parbitmap;
  97
  98   this->tag_ids = tag_ids;
  99   tag_names = new std::vector<std::string>();
 100   tag_names->resize(tag_ids->size());
 101   for(auto val : *(this->tag_ids))
 102     (*this->tag_names)[val.second] = val.first;
 103
 104   uint32_t max_tag = tag_names->size() - 1;
 105   static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();
 106   alphabet_mapper *am = new alphabet_mapper_none();
 107
 108   this->tags = new static_sequence_bs((uint32_t*)&((*tags)[0]), npar, am, bmb);
 109   bits_per_tag = bits8(max_tag);
 110   tag_seq_len = npar;
 111   tag_seq = new uint32_t[uint_len(bits_per_tag, tag_seq_len)];
 112   for(size_t i = 0; i < (size_t) tag_seq_len; i++)
 113     set_field(tag_seq, bits_per_tag, i, (uint32_t) (*tags)[i]);
 114
 115   delete tags;
 116
 117   if (disable_tc) {
 118     text_positions = 0;
 119     text_collection = 0;
 120   } else {
 121     textbitmap->pack();
 122     uint32_t * textbm = textbitmap->get_vector_ptr();
 123     text_positions = new static_bitsequence_rrr02(textbm,
 124                                                   npar,
 125                                                   32);
 126     //delete [] textbm;
 127     //delete textbitmap;
 128
 129     this->text_index_type = idx_type;
 130     text_collection = tc_builder->InitTextCollection();
 131     delete tc_builder;
 132   };
 133
 134
 135 }
 136
 137 xml_tree::~xml_tree()
 138 {
 139   bp_delete(par);
 140   delete tags;
 141   delete [] tag_seq;
 142   delete tag_names;
 143   delete tag_ids;
 144
 145   if (text_collection) delete text_collection;
 146   if (text_positions) delete text_positions;
 147 }
 148
 149 bool xml_tree::is_child(xml_tree::node_t x, xml_tree::node_t y) const
 150 {
 151   return !is_leaf(x) && is_ancestor(y, x) && depth(x)+1 == depth(y);
 152 }
 153
 154 uint32_t xml_tree::depth(xml_tree::node_t x) const
 155 {
 156   return bp_depth(this->par, x);
 157 }
 158
 159
 160 uint32_t xml_tree::preorder(xml_tree::node_t x) const
 161 {
 162   return bp_preorder_rank(this->par, x);
 163 }
 164
 165 uint32_t xml_tree::postorder(xml_tree::node_t x) const
 166 {
 167   return bp_postorder_rank(this->par, x);
 168 }
 169
 170 xml_tree::node_t
 171 xml_tree::select_child(xml_tree::node_t x, xml_tree::tag_t *tags) const
 172 {
 173   if (is_nil(x) || is_leaf(x)) return xml_tree::NIL;
 174   xml_tree::node_t child = first_child(x);
 175   if (array_mem(tags, tag(child))) return child;
 176   return select_sibling(child, tags);
 177 }
 178
 179 xml_tree::node_t
 180 xml_tree::select_descendant(xml_tree::node_t x, xml_tree::tag_t *tags) const
 181 {
 182   if (is_leaf(x)) return xml_tree::NIL;
 183   auto min = xml_tree::NIL;
 184   auto aux = xml_tree::NIL;
 185   for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
 186     aux = tagged_descendant(x, *tags);
 187     if ((unsigned int) aux < (unsigned int) min) min = aux;
 188   };
 189   return min;
 190 }
 191
 192 xml_tree::node_t
 193 xml_tree::select_sibling(xml_tree::node_t x, xml_tree::tag_t *tags) const
 194 {
 195   xml_tree::node_t sibling = next_sibling(x);
 196   xml_tree::tag_t t;
 197   while(!is_nil(sibling)) {
 198     t = tag(sibling);
 199     if (array_mem(tags, t)) return sibling;
 200     sibling = next_sibling(sibling);
 201   };
 202   return sibling;
 203 }
 204
 205 xml_tree::node_t
 206 xml_tree::select_following_before(xml_tree::node_t x, xml_tree::tag_t *tags,
 207                                   xml_tree::node_t limit) const
 208 {
 209   auto min = xml_tree::NIL;
 210   auto aux = xml_tree::NIL;
 211   for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
 212     aux = tagged_following_before(x, *tags, limit);
 213     if ((unsigned int) aux < (unsigned int) min) min = aux;
 214   }
 215   return min;
 216 }
 217
 218 void xml_tree::save(int fd, char* s)
 219 {
 220   FILE* fp;
 221   int fd2 = dup(fd);
 222
 223   fp = fdopen(fd2, "w");
 224
 225   if (fd == 0) throw(std::runtime_error(strerror(errno)));
 226   saveTree(par, fp); //TODO use new api
 227
 228   int ntags = tag_names->size();
 229
 230   ufwrite(&ntags, sizeof(int), 1, fp);
 231   for (int i = 0; i < ntags;i++)
 232     fprintf(fp, "%s\n", tag_names->at(i).c_str());
 233
 234   tags->save(fp);
 235
 236   ufwrite(&bits_per_tag, sizeof(uint),1,fp);
 237   ufwrite(&tag_seq_len, sizeof(uint),1,fp);
 238   ufwrite(tag_seq, sizeof(uint), uint_len(bits_per_tag, tag_seq_len), fp);
 239
 240   bool disable_tc = text_collection == 0 || text_positions == 0;
 241
 242   ufwrite(&disable_tc, sizeof(bool),1,fp);
 243
 244   if (!disable_tc) {
 245     text_positions->save(fp);
 246     ufwrite(&text_index_type,
 247             sizeof(TextCollectionBuilder::index_type_t),
 248             1, fp);
 249
 250     std::string file(s);
 251     switch (text_index_type){
 252     case TextCollectionBuilder::index_type_default:
 253       file.append("_default");
 254       break;
 255     case TextCollectionBuilder::index_type_swcsa:
 256       file.append("_swcsa");
 257       break;
 258     case TextCollectionBuilder::index_type_rlcsa:
 259       file.append("_rlcsa");
 260       break;
 261     };
 262
 263     text_collection->Save(fp, file.c_str());
 264   };
 265
 266   fflush(fp);
 267   fclose(fp);
 268
 269 }
 270
 271 xml_tree* xml_tree::load(int fd, char* name, bool load_tc, int sf)
 272 {
 273   FILE *fp;
 274   char buffer[1024];
 275
 276   int i;
 277   buffer[1023] = '\0';
 278   fp = fdopen(fd, "r");
 279   xml_tree *tree = new xml_tree();
 280
 281   tree->par = loadTree(fp); //TODO use new api
 282   tree->tag_names = new std::vector<std::string>();
 283   tree->tag_ids = new std::unordered_map<std::string, xml_tree::tag_t>();
 284   std::string s;
 285   int ntags;
 286
 287   ufread(&ntags, sizeof(int), 1, fp);
 288
 289   for (i = 0; i < ntags; i++) {
 290     if (fgets(buffer, 1022, fp) != buffer)
 291       throw std::runtime_error("xml_tree::load: cannot read tag list");
 292     s = buffer;
 293     // remove the trailing \n
 294     s.erase(s.size()-1);
 295     tree->tag_names->push_back(s);
 296     tree->tag_ids->insert(std::make_pair(s,
 297                                          static_cast<xml_tree::tag_t>(i)));
 298
 299   };
 300
 301   tree->tags = static_sequence::load(fp);
 302   ufread(&tree->bits_per_tag, sizeof(uint), 1, fp);
 303   fprintf(stderr, "\nBits per tag: %u\n", tree->bits_per_tag);
 304   ufread(&tree->tag_seq_len, sizeof(uint), 1, fp);
 305   size_t size = uint_len(tree->bits_per_tag, tree->tag_seq_len);
 306   tree->tag_seq = new uint[size];
 307   ufread(tree->tag_seq, sizeof(uint), size, fp);
 308
 309   bool disable_tc;
 310   ufread(&disable_tc, sizeof(bool), 1, fp);
 311
 312   if (disable_tc || !load_tc) {
 313     tree->text_positions = 0;
 314     tree->text_collection = 0;
 315   } else {
 316
 317     tree->text_positions = static_bitsequence_rrr02::load(fp);
 318
 319     ufread(&tree->text_index_type,
 320            sizeof(TextCollectionBuilder::index_type_t), 1, fp);
 321
 322     std::string file(name);
 323     switch (tree->text_index_type){
 324     case TextCollectionBuilder::index_type_default:
 325       file.append("_default");
 326       break;
 327     case TextCollectionBuilder::index_type_swcsa:
 328       file.append("_swcsa");
 329       break;
 330     case TextCollectionBuilder::index_type_rlcsa:
 331       file.append("_rlcsa");
 332       break;
 333     };
 334
 335
 336     tree->text_collection =
 337       TextCollection::Load(fp,
 338                            file.c_str(),
 339                            TextCollection::index_mode_default,
 340                            sf);
 341
 342   };
 343   return tree;
 344 }
 345
 346
 347
 348 uint32_t xml_tree::num_children(xml_tree::node_t x) const
 349 {
 350   return bp_degree(par, x);
 351 }
 352
 353 uint32_t xml_tree::child_pos(xml_tree::node_t x) const
 354 {
 355   return bp_child_rank(par, x);
 356 }
 357
 358 xml_tree::node_t xml_tree::child(xml_tree::node_t x, uint32_t i) const
 359 {
 360   if (i < 10) return bp_naive_child(par, x, i);
 361   else bp_child(par, x, i);
 362 }
 363
 364 std::pair<int32_t, int32_t> xml_tree::text_id_range(xml_tree::node_t x) const
 365 {
 366   int32_t i, j;
 367   i = text_positions->rank1(x) - 1;
 368   j = text_positions->rank1(x + 2 * bp_subtree_size(par, x) - 2);
 369   if (i == j)
 370     return std::make_pair(xml_tree::NIL, xml_tree::NIL);
 371   else
 372     return std::make_pair(i + 1, j);
 373 }
 374
 375 int32_t xml_tree::text_id(xml_tree::node_t x) const
 376 {
 377   return (int32_t) text_positions->rank1(x) - 1;
 378 }
 379
 380 unsigned char* xml_tree::get_text(int32_t id) const
 381 {
 382   unsigned char * s = text_collection->GetText(id);
 383   return s + (s[0] == 1);
 384 }
 385
 386 void xml_tree::uflush(int fd)
 387 {
 388   size_t size = print_buffer->size();
 389   if (size < BUFFER_SIZE) return;
 390   uflush_r(fd, size);
 391 }
 392
 393 void xml_tree::flush(int fd)
 394 {
 395   uflush_r(fd, print_buffer->size());
 396 }
 397
 398
 399 void xml_tree::uflush_r(int fd, size_t s)
 400 {
 401   if (s == 0 || print_buffer == 0 || fd <= 0) return;
 402   size_t written;
 403   while (1) {
 404     written = write(fd, print_buffer->data(), s);
 405     if ((written < 0) && (errno == EAGAIN || errno == EINTR)){
 406       continue;
 407     };
 408     break;
 409   };
 410   print_buffer->clear();
 411 }
 412
 413 void xml_tree::uput_str(std::string s, int fd)
 414 {
 415   print_buffer->append(s);
 416   uflush(fd);
 417 }
 418 void xml_tree::uputs(const char* s, int fd)
 419 {
 420   print_buffer->append(s);
 421   uflush(fd);
 422 }
 423 void xml_tree::uputc(const char c, int fd)
 424 {
 425   print_buffer->push_back(c);
 426   uflush(fd);
 427 }
 428
 429 const char * xml_tree::get_tag_name_by_ref(xml_tree::tag_t tagid) const
 430 {
 431
 432    unsigned char *s;
 433    if (tagid < 0 || tagid >= tag_names->size())
 434      return "<INVALID TAG>";
 435
 436    return (const char *) (*tag_names)[tagid].c_str();
 437 }
 438
 439 xml_tree::tag_t xml_tree::register_tag(char *s)
 440 {
 441   auto found = tag_ids->find(std::string(s));
 442   if (found == tag_ids->end())
 443     return xml_tree::NIL_TAG_ID;
 444   else
 445     return (*found).second;
 446 }
 447
 448 size_t xml_tree::uprintf(const char*s, int fd)
 449 {
 450      if (s == 0) return 0;
 451      size_t i;
 452      char c;
 453      for (i = 0; (c = s[i]); i++) {
 454        switch (c) {
 455        case '"':
 456          uputs("&quot;", fd);
 457          break;
 458        case '&':
 459          uputs("&amp;", fd);
 460          break;
 461        case '\'':
 462          uputs("&apos;", fd);
 463          break;
 464        case '<':
 465          uputs("&lt;", fd);
 466          break;
 467        case '>':
 468          uputs("&gt;", fd);
 469          break;
 470        default:
 471          uputc(c, fd);
 472
 473        };
 474      };
 475      return i;
 476 }
 477
 478 // void xml_tree::print(xml_tree::node_t x, int fd, bool no_text)
 479 // {
 480
 481 //   if (print_buffer == 0) {
 482 //     print_buffer = new std::string(BUFFER_SIZE, 0);
 483 //     print_buffer->clear();
 484 //     print_stack = new std::vector<std::string>();
 485 //     print_stack->reserve(256);
 486 //   };
 487
 488 //   xml_tree::node_t fin = bp_find_close(par, x);
 489 //   xml_tree::node_t n = x;
 490 //   xml_tree::tag_t label = tag(n);
 491 //   unsigned char * orig_text;
 492 //   unsigned char * current_text;
 493
 494 //   auto r = text_id_range(x);
 495 //   if (r.first == xml_tree::NIL)
 496 //     current_text = 0;
 497 //   else
 498 //     current_text = text_collection->GetText(r.first, r.second);
 499 //   current_text += (current_text[0] == 1);
 500
 501 //   orig_text = current_text;
 502
 503 //   size_t read = 0;
 504
 505 //   while (n <= fin) {
 506
 507 //     if (bp_inspect(par, n)) {
 508 //       if (label == xml_tree::PCDATA_OPEN_TAG_ID){
 509 //         if (no_text) {
 510 //           uputs("<$/>", fd);
 511 //         } else {
 512 //           read = uprintf( (const char*) current_text, fd);
 513 //           current_text += read + 1;
 514 //         };
 515 //         n += 2; // skip closin $
 516 //         label = tag(n);
 517 //       } else {
 518
 519 //         uputc('<', fd);
 520 //         uput_str((*tag_names)[label], fd);
 521 //         n++;
 522 //         if (bp_inspect(par, n)) {
 523 //           print_stack->push_back((*tag_names)[label]);
 524 //           label = tag(n);
 525 //           if (label == xml_tree::ATTRIBUTE_OPEN_TAG_ID) {
 526 //             n++;
 527 //             if (no_text) uputs("><@@>", fd);
 528
 529 //             while (bp_inspect(par, n))
 530 //               if (no_text) {
 531 //                 uputc('<', fd);
 532 //                 uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 533 //                 uputc('>', fd);
 534 //                 uputs("<$@/></", fd);
 535 //                 uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 536 //                 uputc('>', fd);
 537 //                 n += 4;
 538 //               } else {
 539 //                 uputc(' ', fd);
 540 //                 uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 541 //                 n++;
 542 //                 uputs("=\"", fd);
 543 //                 read = uprintf((const char*) current_text, fd);
 544 //                 current_text += read + 1;
 545 //                 uputc('"', fd);
 546 //                 n += 3;
 547 //               };
 548
 549 //             if (no_text)
 550 //               uputs("</@@>", fd);
 551 //             else uputc('>', fd);
 552 //             n++;
 553 //             label = tag(n);
 554 //           } else
 555 //             uputc('>', fd);
 556 //         } else {
 557 //           uputs("/>", fd);
 558 //           n++;
 559 //           label = tag(n);
 560 //         };
 561 //       };
 562 //     } else do {
 563 //       uputs("</", fd);
 564 //       uput_str(print_stack->back(), fd);
 565 //       uputc('>', fd);
 566 //       print_stack->pop_back();
 567 //       n++;
 568 //       } while (!bp_inspect(par, n) && !print_stack->empty());
 569 //     label = tag(n);
 570 //   };
 571 //   uputc('\n', fd);
 572 //   if (orig_text && text_index_type != TextCollectionBuilder::index_type_default)
 573 //     if (*orig_text == '\0')
 574 //       text_collection->DeleteText(orig_text - 1);
 575 //     else
 576 //       text_collection->DeleteText(orig_text);
 577
 578 // }
 579 void xml_tree::print(xml_tree::node_t x, int fd, bool no_text)
 580 {
 581   for (int i = 0; i < 50; i++)
 582     fprintf(stderr, "Printing text number %i: %s\n", i, get_text(i));
 583
 584   if (print_buffer == 0) {
 585     print_buffer = new std::string(BUFFER_SIZE, 0);
 586     print_buffer->clear();
 587     print_stack = new std::vector<std::string>();
 588     print_stack->reserve(256);
 589   };
 590
 591   xml_tree::node_t fin = bp_find_close(par, x);
 592   xml_tree::node_t n = x;
 593   xml_tree::tag_t label = tag(n);
 594   unsigned char * current_text;
 595
 596
 597   while (n <= fin) {
 598
 599     if (bp_inspect(par, n)) {
 600       if (label == xml_tree::PCDATA_OPEN_TAG_ID){
 601         if (no_text) {
 602           uputs("<$/>", fd);
 603         } else {
 604           current_text = get_text(text_id(n));
 605           uprintf( (const char*) (current_text + (current_text[0] == 1)), fd);
 606
 607           if (current_text && text_index_type != TextCollectionBuilder::index_type_default)
 608             text_collection->DeleteText(current_text);
 609
 610           n += 2; // skip closin $
 611           label = tag(n);
 612         };
 613       } else {
 614           uputc('<', fd);
 615           uput_str((*tag_names)[label], fd);
 616           n++;
 617           if (bp_inspect(par, n)) {
 618             print_stack->push_back((*tag_names)[label]);
 619             label = tag(n);
 620             if (label == xml_tree::ATTRIBUTE_OPEN_TAG_ID) {
 621               n++;
 622               if (no_text) uputs("><@@>", fd);
 623
 624               while (bp_inspect(par, n))
 625                 if (no_text) {
 626                   uputc('<', fd);
 627                   uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 628                   uputc('>', fd);
 629                   uputs("<$@/></", fd);
 630                   uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 631                   uputc('>', fd);
 632                   n += 4;
 633                 } else {
 634                   uputc(' ', fd);
 635                   uputs((const char*) &(get_tag_name_by_ref(tag(n))[3]), fd);
 636                   n+= 2;
 637                   uputs("=\"", fd);
 638                   current_text = get_text(text_id(n));
 639                   uprintf((const char*) (current_text + (current_text[0] == 1)), fd);
 640                   if (current_text && text_index_type != TextCollectionBuilder::index_type_default)
 641                       text_collection->DeleteText(current_text);
 642                   uputc('"', fd);
 643                   n += 2;
 644                 };
 645
 646               if (no_text)
 647                 uputs("</@@>", fd);
 648               else uputc('>', fd);
 649               n++;
 650               label = tag(n);
 651             } else
 652               uputc('>', fd);
 653           } else {
 654             uputs("/>", fd);
 655             n++;
 656             label = tag(n);
 657           };
 658         };
 659       } else do {
 660           uputs("</", fd);
 661           uput_str(print_stack->back(), fd);
 662           uputc('>', fd);
 663           print_stack->pop_back();
 664           n++;
 665         } while (!bp_inspect(par, n) && !print_stack->empty());
 666       label = tag(n);
 667     };
 668   uputc('\n', fd);
 669
 670 }