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