← Back to branch summary

~kosova/+junk/tuxfamily-twiki

« back to all changes in this revision

Viewing changes to foswiki/lib/Foswiki/Query/HoistREs.pm

  • Committer: James Michael DuPont
  • Date: 2009-07-18 19:58:49 UTC
  • Revision ID: jamesmikedupont@gmail.com-20090718195849-vgbmaht2ys791uo2
added foswiki

Show diffs side-by-side

added added

removed removed

Lines of Context:
foswiki/lib/Foswiki/Query/HoistREs.pm
 
1
# See bottom of file for copyright and license details
 
2
 
 
3
=begin TML
 
4
 
 
5
---+ package Foswiki::Query::HoistREs
 
6
 
 
7
Static functions to extract regular expressions from queries. The REs can
 
8
be used in caching stores that use the Foswiki standard inline meta-data
 
9
representation to pre-filter topic lists for more efficient query matching.
 
10
 
 
11
See =Store/RcsFile.pm= for an example of usage.
 
12
 
 
13
=cut
 
14
 
 
15
package Foswiki::Query::HoistREs;
 
16
 
 
17
use strict;
 
18
 
 
19
use Foswiki::Infix::Node;
 
20
use Foswiki::Query::Node;
 
21
 
 
22
# Try to optimise a query by hoisting regular expression searches
 
23
# out of the query
 
24
#
 
25
# patterns we need to look for:
 
26
#
 
27
# top level is defined by a sequence of AND and OR conjunctions
 
28
# second level, = and ~
 
29
# second level LHS is a field access
 
30
# second level RHS is a static string or number
 
31
 
 
32
sub MONITOR_HOIST { 0 }
 
33
 
 
34
=begin TML
 
35
 
 
36
---++ ObjectMethod hoist($query) -> @res
 
37
 
 
38
Extract useful filter REs from the given query. The list returned is a list
 
39
of filter expressions that can be used with a cache search to refine the
 
40
list of topics. The full query should still be applied to topics that remain
 
41
after the filter match has been applied; this is purely an optimisation.
 
42
 
 
43
=cut
 
44
 
 
45
sub hoist {
 
46
    my $node = shift;
 
47
 
 
48
    return () unless ref( $node->{op} );
 
49
 
 
50
    if ( $node->{op}->{name} eq '(' ) {
 
51
        return hoist( $node->{params}[0] );
 
52
    }
 
53
 
 
54
    print STDERR "hoist ", $node->stringify(), "\n" if MONITOR_HOIST;
 
55
    if ( $node->{op}->{name} eq 'and' ) {
 
56
        my @lhs = hoist( $node->{params}[0] );
 
57
        my $rhs = _hoistOR( $node->{params}[1] );
 
58
        if ( scalar(@lhs) && $rhs ) {
 
59
            return ( @lhs, $rhs );
 
60
        }
 
61
        elsif ( scalar(@lhs) ) {
 
62
            return @lhs;
 
63
        }
 
64
        elsif ($rhs) {
 
65
            return ($rhs);
 
66
        }
 
67
    }
 
68
    else {
 
69
        my $or = _hoistOR($node);
 
70
        return ($or) if $or;
 
71
    }
 
72
 
 
73
    print STDERR "\tFAILED\n" if MONITOR_HOIST;
 
74
    return ();
 
75
}
 
76
 
 
77
# depth 1; we can handle a sequence of ORs
 
78
sub _hoistOR {
 
79
    my $node = shift;
 
80
 
 
81
    return undef unless ref( $node->{op} );
 
82
 
 
83
    if ( $node->{op}->{name} eq '(' ) {
 
84
        return _hoistOR( $node->{params}[0] );
 
85
    }
 
86
 
 
87
    print STDERR "hoistOR ", $node->stringify(), "\n" if MONITOR_HOIST;
 
88
 
 
89
    if ( $node->{op}->{name} eq 'or' ) {
 
90
        my $lhs = _hoistOR( $node->{params}[0] );
 
91
        my $rhs = _hoistEQ( $node->{params}[1] );
 
92
        if ( $lhs && $rhs ) {
 
93
            return "$lhs|$rhs";
 
94
        }
 
95
    }
 
96
    else {
 
97
        return _hoistEQ($node);
 
98
    }
 
99
 
 
100
    print STDERR "\tFAILED\n" if MONITOR_HOIST;
 
101
    return undef;
 
102
}
 
103
 
 
104
# depth 2: can handle = and ~ expressions
 
105
sub _hoistEQ {
 
106
    my $node = shift;
 
107
 
 
108
    return undef unless ref( $node->{op} );
 
109
 
 
110
    if ( $node->{op}->{name} eq '(' ) {
 
111
        return _hoistEQ( $node->{params}[0] );
 
112
    }
 
113
 
 
114
    print STDERR "hoistEQ ", $node->stringify(), "\n" if MONITOR_HOIST;
 
115
 
 
116
    # \000RHS\001 is a placholder for the RHS term
 
117
    if ( $node->{op}->{name} eq '=' ) {
 
118
        my $lhs = _hoistDOT( $node->{params}[0] );
 
119
        my $rhs = _hoistConstant( $node->{params}[1] );
 
120
        if ( $lhs && $rhs ) {
 
121
            $rhs = quotemeta($rhs);
 
122
            $lhs =~ s/\000RHS\001/$rhs/g;
 
123
            return $lhs;
 
124
        }
 
125
 
 
126
        # = is symmetric, so try the other order
 
127
        $lhs = _hoistDOT( $node->{params}[1] );
 
128
        $rhs = _hoistConstant( $node->{params}[0] );
 
129
        if ( $lhs && $rhs ) {
 
130
            $rhs = quotemeta($rhs);
 
131
            $lhs =~ s/\000RHS\001/$rhs/g;
 
132
            return $lhs;
 
133
        }
 
134
    }
 
135
    elsif ( $node->{op}->{name} eq '~' ) {
 
136
        my $lhs = _hoistDOT( $node->{params}[0] );
 
137
        my $rhs = _hoistConstant( $node->{params}[1] );
 
138
        if ( $lhs && $rhs ) {
 
139
            $rhs = quotemeta($rhs);
 
140
            $rhs =~ s/\\\?/./g;
 
141
            $rhs =~ s/\\\*/.*/g;
 
142
            $lhs =~ s/\000RHS\001/$rhs/g;
 
143
            return $lhs;
 
144
        }
 
145
    }
 
146
 
 
147
    print STDERR "\tFAILED\n" if MONITOR_HOIST;
 
148
    return undef;
 
149
}
 
150
 
 
151
# Expecting a (root level) field access expression. This must be of the form
 
152
# <name>
 
153
# or
 
154
# <rootfield>.<name>
 
155
# <rootfield> may be aliased
 
156
sub _hoistDOT {
 
157
    my $node = shift;
 
158
 
 
159
    if ( ref( $node->{op} ) && $node->{op}->{name} eq '(' ) {
 
160
        return _hoistDOT( $node->{params}[0] );
 
161
    }
 
162
 
 
163
    print STDERR "hoistDOT ", $node->stringify(), "\n" if MONITOR_HOIST;
 
164
    if ( ref( $node->{op} ) && $node->{op}->{name} eq '.' ) {
 
165
        my $lhs = $node->{params}[0];
 
166
        my $rhs = $node->{params}[1];
 
167
        if (   !ref( $lhs->{op} )
 
168
            && !ref( $rhs->{op} )
 
169
            && $lhs->{op} eq $Foswiki::Infix::Node::NAME
 
170
            && $rhs->{op} eq $Foswiki::Infix::Node::NAME )
 
171
        {
 
172
            $lhs = $lhs->{params}[0];
 
173
            $rhs = $rhs->{params}[0];
 
174
            if ( $Foswiki::Query::Node::aliases{$lhs} ) {
 
175
                $lhs = $Foswiki::Query::Node::aliases{$lhs};
 
176
            }
 
177
            if ( $lhs =~ /^META:/ ) {
 
178
 
 
179
                # \000RHS\001 is a placholder for the RHS term
 
180
                return '^%' . $lhs . '{.*\\b' . $rhs . "=\\\"\000RHS\001\\\"";
 
181
            }
 
182
 
 
183
            # Otherwise assume the term before the dot is the form name
 
184
            if ( $rhs eq 'text' ) {
 
185
 
 
186
                # Special case for the text body
 
187
                return "\000RHS\001";
 
188
            }
 
189
            else {
 
190
                return
 
191
"^%META:FIELD{name=\\\"$rhs\\\".*\\bvalue=\\\"\000RHS\001\\\"";
 
192
            }
 
193
 
 
194
        }
 
195
    }
 
196
    elsif ( !ref( $node->{op} ) && $node->{op} eq $Foswiki::Infix::Node::NAME ) {
 
197
        if ( $node->{params}[0] eq 'name' ) {
 
198
 
 
199
            # Special case for the topic name
 
200
            return undef;
 
201
        }
 
202
        elsif ( $node->{params}[0] eq 'web' ) {
 
203
 
 
204
            # Special case for the web name
 
205
            return undef;
 
206
        }
 
207
        elsif ( $node->{params}[0] eq 'text' ) {
 
208
 
 
209
            # Special case for the text body
 
210
            return "\000RHS\001";
 
211
        }
 
212
        else {
 
213
            return
 
214
"^%META:FIELD{name=\\\"$node->{params}[0]\\\".*\\bvalue=\\\"\0RHS\1\\\"";
 
215
        }
 
216
    }
 
217
 
 
218
    print STDERR "\tFAILED\n" if MONITOR_HOIST;
 
219
    return undef;
 
220
}
 
221
 
 
222
# Expecting a constant
 
223
sub _hoistConstant {
 
224
    my $node = shift;
 
225
 
 
226
    if (
 
227
        !ref( $node->{op} )
 
228
        && (   $node->{op} eq $Foswiki::Infix::Node::STRING
 
229
            || $node->{op} eq $Foswiki::Infix::Node::NUMBER )
 
230
      )
 
231
    {
 
232
        return $node->{params}[0];
 
233
    }
 
234
    return undef;
 
235
}
 
236
 
 
237
1;
 
238
__DATA__
 
239
 
 
240
Module of Foswiki - The Free and Open Source Wiki, http://foswiki.org/, http://Foswiki.org/
 
241
 
 
242
# Copyright (C) 2008-2009 Foswiki Contributors. All Rights Reserved.
 
243
# Foswiki Contributors are listed in the AUTHORS file in the root
 
244
# of this distribution. NOTE: Please extend that file, not this notice.
 
245
#
 
246
# Additional copyrights apply to some or all of the code in this
 
247
# file as follows:
 
248
#
 
249
# Copyright (C) 2005-2007 TWiki Contributors. All Rights Reserved.
 
250
# TWiki Contributors are listed in the AUTHORS file in the root
 
251
# of this distribution. NOTE: Please extend that file, not this notice.
 
252
#
 
253
This program is free software; you can redistribute it and/or
 
254
modify it under the terms of the GNU General Public License
 
255
as published by the Free Software Foundation; either version 2
 
256
of the License, or (at your option) any later version. For
 
257
more details read LICENSE in the root of this distribution.
 
258
 
 
259
This program is distributed in the hope that it will be useful,
 
260
but WITHOUT ANY WARRANTY; without even the implied warranty of
 
261
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
262
 
 
263
As per the GPL, removal of this notice is prohibited.
 
264
 
 
265
Author: Crawford Currie http://c-dot.co.uk