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