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