← Back to branch summary

~ubuntu-branches/ubuntu/precise/evolution/precise

« back to all changes in this revision

Viewing changes to widgets/misc/e-searching-tokenizer.c

  • Committer: Package Import Robot
  • Author(s): Mathieu Trudel-Lapierre
  • Date: 2011-09-08 09:38:57 UTC
  • mfrom: (1.1.84 upstream)
  • Revision ID: package-import@ubuntu.com-20110908093857-6lfl04ke2ns3kx2o
Tags: 3.1.91-0ubuntu1
https://launchpad.net/bugs/843769
* New upstream release. (LP: #843769)
* debian/control: bump e-d-s Build-Depends to 3.1.91. 

Show diffs side-by-side

added added

removed removed

Lines of Context:
widgets/misc/e-searching-tokenizer.c
56
56
static inline guint32
57
57
camel_utf8_getc (const guchar **ptr)
58
58
{
59
 
        register guchar *p = (guchar *)*ptr;
 
59
        register guchar *p = (guchar *) * ptr;
60
60
        register guchar c, r;
61
61
        register guint32 v, m;
62
62
 
75
75
                                r = c;
76
76
                                goto loop;
77
77
                        }
78
 
                        v = (v<<6) | (c & 0x3f);
 
78
                        v = (v << 6) | (c & 0x3f);
79
79
                        r<<=1;
80
80
                        m<<=5;
81
81
                } while (r & 0x40);
93
93
/* note: our tags of interest are 7 bit ascii
94
94
 * only no need to do any fancy utf8 stuff */
95
95
/* tags should be upper case
96
 
   if this list gets longer than 10 entries, consider binary search */
 
96
 * if this list gets longer than 10 entries, consider binary search */
97
97
static const gchar *ignored_tags[] = {
98
98
        "B", "I", "FONT", "TT", "EM", /* and more? */};
99
99
 
100
100
static gint
101
101
ignore_tag (const gchar *tag)
102
102
{
103
 
        gchar *t = g_alloca (strlen (tag)+1), c, *out;
 
103
        gchar *t = g_alloca (strlen (tag) + 1), c, *out;
104
104
        const gchar *in;
105
105
        gint i;
106
106
 
107
107
        /* we could use a aho-corasick matcher here too ... but we wont */
108
108
 
109
109
        /* normalise tag into 't'.
110
 
           Note we use the property that the only tags we're interested in
111
 
           are 7 bit ascii to shortcut and simplify case insensitivity */
 
110
         * Note we use the property that the only tags we're interested in
 
111
         * are 7 bit ascii to shortcut and simplify case insensitivity */
112
112
        in = tag+2;             /* skip: TAG_ESCAPE '<' */
113
113
        if (*in == '/')
114
114
                in++;
163
163
/* will be enabled only if debug is enabled */
164
164
#if d(1) -1 != -1
165
165
static void
166
 
dump_trie (struct _state *s, gint d)
 
166
dump_trie (struct _state *s,
 
167
           gint d)
167
168
{
168
 
        gchar *p = g_alloca (d*2+1);
 
169
        gchar *p = g_alloca (d *2 + 1);
169
170
        struct _match *m;
170
171
 
171
 
        memset (p, ' ', d*2);
172
 
        p[d*2]=0;
 
172
        memset (p, ' ', d *2);
 
173
        p[d *2]=0;
173
174
 
174
175
        printf("%s[state] %p: %d  fail->%p\n", p, s, s->final, s->fail);
175
176
        m = s->matches;
176
177
        while (m) {
177
178
                printf(" %s'%c' -> %p\n", p, m->ch, m->match);
178
179
                if (m->match)
179
 
                        dump_trie (m->match, d+1);
 
180
                        dump_trie (m->match, d + 1);
180
181
                m = m->next;
181
182
        }
182
183
}
184
185
 
185
186
/* This builds an Aho-Corasick search trie for a set of utf8 words */
186
187
/* See
187
 
    http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html
188
 
   for a neat demo */
 
188
 *  http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html
 
189
 * for a neat demo */
189
190
 
190
191
static inline struct _match *
191
 
g (struct _state *q, guint32 c)
 
192
g (struct _state *q,
 
193
   guint32 c)
192
194
{
193
195
        struct _match *m = q->matches;
194
196
 
199
201
}
200
202
 
201
203
static struct _trie *
202
 
build_trie (gint nocase, gint len, guchar **words)
 
204
build_trie (gint nocase,
 
205
            gint len,
 
206
            guchar **words)
203
207
{
204
208
        struct _state *q, *qt, *r;
205
209
        const guchar *word;
222
226
        /* This will correspond to the length of the longest pattern */
223
227
        state_depth_size = 0;
224
228
        state_depth_max = 64;
225
 
        state_depth = g_malloc (sizeof (*state_depth[0])*64);
 
229
        state_depth = g_malloc (sizeof (*state_depth[0]) * 64);
226
230
        state_depth[0] = NULL;
227
231
 
228
232
        /* Step 1: Build trie */
229
233
 
230
234
        /* This just builds a tree that merges all common prefixes into the same branch */
231
235
 
232
 
        for (i=0;i<len;i++) {
 
236
        for (i = 0; i < len; i++) {
233
237
                word = words[i];
234
238
                q = &trie->root;
235
239
                depth = 0;
277
281
         * find multiple substrings concurrently, using aho-corasick's
278
282
         * algorithm. */
279
283
 
280
 
        for (i=0;i<state_depth_size;i++) {
 
284
        for (i = 0; i < state_depth_size; i++) {
281
285
                q = state_depth[i];
282
286
                while (q) {
283
287
                        m = q->matches;
401
405
        s->tage = g_strdup (tage);
402
406
        s->flags = flags;
403
407
        s->state = &s->t->root;
404
 
        s->matchcount = 0;
 
408
        s->matchcount = -1;
405
409
 
406
410
        g_queue_init (&s->input);
407
411
        g_queue_init (&s->output);
411
415
        s->offout = 0;
412
416
 
413
417
        /* rotating queue of previous character positions */
414
 
        m = s->t->max_depth+1;
 
418
        m = s->t->max_depth + 1;
415
419
        i = 2;
416
 
        while (i<m)
 
420
        while (i < m)
417
421
                i<<=2;
418
 
        s->last = g_malloc (sizeof (s->last[0])*i);
419
 
        s->last_mask = i-1;
 
422
        s->last = g_malloc (sizeof (s->last[0]) * i);
 
423
        s->last_mask = i - 1;
420
424
        s->lastp = 0;
421
425
 
422
426
        /* a stack of possible submatches */
423
427
        s->submatchp = 0;
424
 
        s->submatches = g_malloc (sizeof (s->submatches[0])*argc+1);
 
428
        s->submatches = g_malloc (sizeof (s->submatches[0]) * argc + 1);
425
429
 
426
430
        return s;
427
431
}
444
448
}
445
449
 
446
450
static struct _token *
447
 
append_token (GQueue *queue, const gchar *tok, gint len)
 
451
append_token (GQueue *queue,
 
452
              const gchar *tok,
 
453
              gint len)
448
454
{
449
455
        struct _token *token;
450
456
 
451
457
        if (len == -1)
452
458
                len = strlen (tok);
453
 
        token = g_malloc (sizeof (*token) + len+1);
 
459
        token = g_malloc (sizeof (*token) + len + 1);
454
460
        token->offset = 0;      /* set by caller when required */
455
461
        memcpy (token->tok, tok, len);
456
462
        token->tok[len] = 0;
462
468
#define free_token(x) (g_free (x))
463
469
 
464
470
static void
465
 
output_token (struct _searcher *s, struct _token *token)
 
471
output_token (struct _searcher *s,
 
472
              struct _token *token)
466
473
{
467
474
        gint offend;
468
475
        gint left, pre;
475
482
                }
476
483
        } else {
477
484
                offend = token->offset + strlen (token->tok);
478
 
                left = offend-s->offout;
 
485
                left = offend - s->offout;
479
486
                if (left > 0) {
480
487
                        pre = s->offout - token->offset;
481
 
                        if (pre>0)
482
 
                                memmove (token->tok, token->tok+pre, left+1);
 
488
                        if (pre > 0)
 
489
                                memmove (token->tok, token->tok + pre, left + 1);
483
490
                        s->offout = offend;
484
491
                        g_queue_push_tail (&s->output, token);
485
492
                } else {
489
496
}
490
497
 
491
498
static struct _token *
492
 
find_token (struct _searcher *s, gint start)
 
499
find_token (struct _searcher *s,
 
500
            gint start)
493
501
{
494
502
        GList *link;
495
503
 
508
516
}
509
517
 
510
518
static void
511
 
output_match (struct _searcher *s, guint start, guint end)
 
519
output_match (struct _searcher *s,
 
520
              guint start,
 
521
              guint end)
512
522
{
513
523
        register struct _token *token;
514
524
        struct _token *starttoken, *endtoken;
534
544
        if (s->offout < start) {
535
545
                token = append_token (
536
546
                        &s->output, starttoken->tok +
537
 
                        (s->offout-starttoken->offset),
538
 
                        start-s->offout);
 
547
                        (s->offout - starttoken->offset),
 
548
                        start - s->offout);
539
549
                s->offout = start;
540
550
        }
541
551
 
559
569
        if (s->offout < end) {
560
570
                token = append_token (
561
571
                        &s->output, endtoken->tok +
562
 
                        (s->offout-endtoken->offset),
563
 
                        end-s->offout);
 
572
                        (s->offout - endtoken->offset),
 
573
                        end - s->offout);
564
574
                s->offout = end;
565
575
        }
566
576
 
581
591
{
582
592
        gint i;
583
593
 
584
 
        for (i=s->submatchp-1;i>=0;i--)
 
594
        for (i = s->submatchp - 1; i >= 0; i--)
585
595
                output_match (s, s->submatches[i].offstart, s->submatches[i].offend);
586
596
        s->submatchp = 0;
587
597
}
588
598
 
589
599
/* returns true if a merge took place */
590
600
static gint
591
 
merge_subpending (struct _searcher *s, gint offstart, gint offend)
 
601
merge_subpending (struct _searcher *s,
 
602
                  gint offstart,
 
603
                  gint offend)
592
604
{
593
605
        gint i;
594
606
 
595
607
        /* merges overlapping or abutting match strings */
596
608
        if (s->submatchp &&
597
 
            s->submatches[s->submatchp-1].offend >= offstart) {
 
609
            s->submatches[s->submatchp - 1].offend >= offstart) {
598
610
 
599
611
                /* go from end, any that match 'invalidate' follow-on ones too */
600
 
                for (i=s->submatchp-1;i>=0;i--) {
 
612
                for (i = s->submatchp - 1; i >= 0; i--) {
601
613
                        if (s->submatches[i].offend >= offstart) {
602
614
                                if (offstart < s->submatches[i].offstart)
603
615
                                        s->submatches[i].offstart = offstart;
604
616
                                s->submatches[i].offend = offend;
605
617
                                if (s->submatchp > i)
606
 
                                        s->submatchp = i+1;
 
618
                                        s->submatchp = i + 1;
607
619
                        }
608
620
                }
609
621
                return 1;
613
625
}
614
626
 
615
627
static void
616
 
push_subpending (struct _searcher *s, gint offstart, gint offend)
 
628
push_subpending (struct _searcher *s,
 
629
                 gint offstart,
 
630
                 gint offend)
617
631
{
618
632
        /* This is really an assertion, we just ignore the
619
633
         * last pending match instead of crashing though. */
620
634
        if (s->submatchp >= s->words) {
621
635
                d (printf("ERROR: submatch pending stack overflow\n"));
622
 
                s->submatchp = s->words-1;
 
636
                s->submatchp = s->words - 1;
623
637
        }
624
638
 
625
639
        s->submatches[s->submatchp].offstart = offstart;
648
662
 
649
663
        /* find earliest gchar that can be in contention */
650
664
        start = s->offset - s->t->max_depth;
651
 
        for (i=0;i<s->submatchp;i++)
 
665
        for (i = 0; i < s->submatchp; i++)
652
666
                if (s->submatches[i].offstart < start)
653
667
                        start = s->submatches[i].offstart;
654
668
 
713
727
                                q = &t->root;
714
728
                        } else if (m != NULL) {
715
729
                                /* keep track of previous offsets of utf8 chars, rotating buffer */
716
 
                                s->last[s->lastp] = s->offset + (pre_tok-stok);
717
 
                                s->lastp = (s->lastp+1)&s->last_mask;
 
730
                                s->last[s->lastp] = s->offset + (pre_tok - stok);
 
731
                                s->lastp = (s->lastp + 1) &s->last_mask;
718
732
 
719
733
                                q = m->match;
720
734
                                /* we have a match of q->final characters for a matching word */
722
736
                                        s->matchcount++;
723
737
 
724
738
                                        /* use the last buffer to find the real offset of this gchar */
725
 
                                        offstart = s->last[(s->lastp - q->final)&s->last_mask];
 
739
                                        offstart = s->last[(s->lastp - q->final) &s->last_mask];
726
740
                                        offend = s->offset + (tok - stok);
727
741
 
728
742
                                        if (q->matches == NULL) {
752
766
                        pre_tok = tok;
753
767
                }
754
768
 
755
 
                s->offset += (pre_tok-stok);
 
769
                s->offset += (pre_tok - stok);
756
770
 
757
771
                flush_extra (s);
758
772
        }
794
808
struct _search_info {
795
809
        GPtrArray *strv;
796
810
        gchar *color;
797
 
        guint size:8;
798
 
        guint flags:8;
 
811
        guint size : 8;
 
812
        guint flags : 8;
799
813
};
800
814
 
801
815
/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/
812
826
}
813
827
 
814
828
static void
815
 
search_info_set_flags (struct _search_info *si, guint flags, guint mask)
 
829
search_info_set_flags (struct _search_info *si,
 
830
                       guint flags,
 
831
                       guint mask)
816
832
{
817
833
        si->flags = (si->flags & ~mask) | (flags & mask);
818
834
}
819
835
 
820
836
static void
821
 
search_info_set_color (struct _search_info *si, const gchar *color)
 
837
search_info_set_color (struct _search_info *si,
 
838
                       const gchar *color)
822
839
{
823
840
        g_free (si->color);
824
841
        si->color = g_strdup (color);
825
842
}
826
843
 
827
844
static void
828
 
search_info_add_string (struct _search_info *si, const gchar *s)
 
845
search_info_add_string (struct _search_info *si,
 
846
                        const gchar *s)
829
847
{
830
848
        const guchar *start;
831
849
        guint32 c;
851
869
{
852
870
        gint i;
853
871
 
854
 
        for (i=0;i<si->strv->len;i++)
 
872
        for (i = 0; i < si->strv->len; i++)
855
873
                g_free (si->strv->pdata[i]);
856
874
 
857
875
        g_ptr_array_set_size (si->strv, 0);
862
880
{
863
881
        gint i;
864
882
 
865
 
        for (i=0;i<si->strv->len;i++)
 
883
        for (i = 0; i < si->strv->len; i++)
866
884
                g_free (si->strv->pdata[i]);
867
885
 
868
886
        g_ptr_array_free (si->strv, TRUE);
877
895
        gint i;
878
896
 
879
897
        out = search_info_new ();
880
 
        for (i=0;i<si->strv->len;i++)
 
898
        for (i = 0; i < si->strv->len; i++)
881
899
                g_ptr_array_add (out->strv, g_strdup (si->strv->pdata[i]));
882
900
        out->color = g_strdup (si->color);
883
901
        out->flags = si->flags;
900
918
        else
901
919
                col = si->color;
902
920
 
903
 
        tags = g_alloca (20+strlen (col));
 
921
        tags = g_alloca (20 + strlen (col));
904
922
        sprintf(tags, "%c<font color=\"%s\">", TAG_ESCAPE, col);
905
923
        tage = g_alloca (20);
906
924
        sprintf(tage, "%c</font>", TAG_ESCAPE);
922
940
/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/
923
941
 
924
942
/* blah blah the htmltokeniser doesn't like being asked
925
 
   for a token if it doens't hvae any! */
 
943
 * for a token if it doens't hvae any! */
926
944
static gchar *
927
945
get_token (HTMLTokenizer *tokenizer)
928
946
{
1019
1037
                        next_token (tokenizer);
1020
1038
 
1021
1039
        oldmatched = priv->engine->matchcount;
 
1040
        if (priv->engine->matchcount == -1)
 
1041
                priv->engine->matchcount = 0;
1022
1042
 
1023
1043
        token = searcher_next_token (priv->engine);
1024
1044