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