Mercurial > genshi > genshi-test

comparison genshi/template/match.py @ 712:385346ae71f0 experimental-match-fastpaths

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
minor performance updates for non-match cases like bigtable, and for any case where before_template/after_template would create an empty MatchSet
author aflett
date Mon, 07 Apr 2008 18:27:55 +0000
parents 4d2afb73d51b
children
comparison
equal deleted inserted replaced
711:470dd4571841 712:385346ae71f0
119 If a given py:match's path is simply a node name match, 119 If a given py:match's path is simply a node name match,
120 (LocalNameTest) like "xyz", then MatchSet indexes that in a 120 (LocalNameTest) like "xyz", then MatchSet indexes that in a
121 dictionary that maps tag names to matches. 121 dictionary that maps tag names to matches.
122 122
123 If the path is more complex like "xyz[k=z]" then then that match 123 If the path is more complex like "xyz[k=z]" then then that match
124 will always be returned by ``find_matches``. """ 124 will always be returned by ``find_matches``.
125
126 """
125 def __init__(self, parent=None, 127 def __init__(self, parent=None,
126 min_index=None, 128 min_index=None,
127 max_index=None): 129 max_index=None):
128 """ 130 """ If a parent is given, it means this is likely a MatchSet
129 If a parent is given, it means this is a wrapper around another 131 constrained by min_index or max_index.
130 set.
131 132
132 """ 133 """
133 if parent is None: 134 if parent is None:
134 self.state = MatchState() 135 self.state = MatchState()
135 else:
136 self.state = parent.state
137
138 if parent is None:
139 self.min_index = None 136 self.min_index = None
140 self.max_index = None 137 self.max_index = None
141 else: 138 else:
142 # We have a parent: Just copy references to member 139 # We have a parent: Just copy references to member
143 # variables in parent so that there's no performance loss 140 # variables in parent so that there's no performance loss
141 self.state = parent.state
144 self.max_index = parent.max_index 142 self.max_index = parent.max_index
145 self.min_index = parent.min_index 143 self.min_index = parent.min_index
146 144
147 # sub-MatchSets can only be further constrained, not expanded 145 # sub-MatchSets can only be further constrained, not expanded
148 if max_index is not None: 146 if max_index is not None:
150 self.max_index = max_index 148 self.max_index = max_index
151 149
152 if min_index is not None: 150 if min_index is not None:
153 assert self.min_index is None or min_index > self.min_index 151 assert self.min_index is None or min_index > self.min_index
154 self.min_index = min_index 152 self.min_index = min_index
153
154 # initialize empty state
155 self.not_empty = self.have_matches()
155 156
156 def add(self, match_template): 157 def add(self, match_template):
157 """ 158 """
158 match_template is a tuple the form 159 match_template is a tuple the form
159 test, path, template, hints, namespace, directives 160 test, path, template, hints, namespace, directives
160 """ 161 """
161 self.state.add(match_template) 162 self.state.add(match_template)
162 163 self.not_empty = self.have_matches()
164
165 # we should never add a new py:match to a constrained
166 # MatchSet, therefore the set should never be empty here
167 assert self.not_empty
163 168
164 def remove(self, match_template): 169 def remove(self, match_template):
165 """ 170 """
166 Permanently remove a match_template - mainly for match_once 171 Permanently remove a match_template - mainly for match_once
167 """ 172 """
168 self.state.remove(match_template) 173 self.state.remove(match_template)
174 self.not_empty = self.have_matches()
169 175
170 def before_template(self, match_template, inclusive): 176 def before_template(self, match_template, inclusive):
171 """ Return a new MatchSet where only the templates that were declared 177 """ Return a new MatchSet where only the templates that were declared
172 before ``match_template`` are available. If ``inclusive`` is 178 before ``match_template`` are available. If ``inclusive`` is
173 true, then it will also include match_template itself. 179 true, then it will also include match_template itself.
191 197
192 def find_matches(self, event): 198 def find_matches(self, event):
193 """ Return a list of all valid templates that can be used for the 199 """ Return a list of all valid templates that can be used for the
194 given event. 200 given event.
195 201
196 The basic work here is sorting the result of find_raw_matches 202 The basic work here is sorting the result of find_raw_matches.
203
197 """ 204 """
198 # remove exclusions 205 # remove exclusions
199 def can_match(template): 206 def can_match(template):
200 # make sure that 207 # make sure that
201 if (self.min_index is not None and 208 if (self.min_index is not None and
213 220
214 # sort the results according to the order they were added 221 # sort the results according to the order they were added
215 return sorted(matches, key=lambda v: self.state.match_order[id(v)]) 222 return sorted(matches, key=lambda v: self.state.match_order[id(v)])
216 223
217 def __nonzero__(self): 224 def __nonzero__(self):
218 """ 225 """ allow this to behave as a list - and at least try to act empty if
219 allow this to behave as a list - and at least try to act empty if 226 the list is likely to be empty.
220 the list is likely to be empty 227
228 """
229 return self.not_empty
230
231 def have_matches(self):
232 """ This function does some O(1) checks for states when this MatchSet
233 absolutely must be empty - such as when there are no py:match
234 templates, or when the max/min index would prohibit any
235 possible match.
236
237 This function should be called whenever the match state is
238 updated (i.e. any time we add/remove a new py:match, create a
239 new MatchSet, etc.) The expectation is that these
240 less-frequent checks are, amortized over a template, are
241 cheaper than calls to find_matches() for any arbitrary path.
242
221 """ 243 """
222 # dirt-simple case: no py:match templates at all 244 # dirt-simple case: no py:match templates at all
223 if not (self.state.tag_templates or self.state.other_templates): 245 if not (self.state.tag_templates or self.state.other_templates):
224 return False 246 return False
247
225 # this is easy - before the first element there is nothing 248 # this is easy - before the first element there is nothing
226 if self.max_index == -1: 249 if (self.max_index is not None and
250 self.max_index < 0):
227 return False 251 return False
228 252
229 # this isn't always right because match_order may shrink, but 253 # we're constrained, but we've removed any templates after min_index
230 # you'll never get a false-negative 254 if (self.min_index is not None and
231 if self.min_index == self.state.current_index: 255 self.min_index > self.state.current_index):
232 return False 256 return False
233 257
234 # check for a range that is completely constrained 258 # check for a range that is completely constrained
235 if self.min_index is not None and self.max_index is not None: 259 if self.min_index is not None and self.max_index is not None:
236 if self.min_index >= self.max_index: 260 if self.min_index >= self.max_index:
237 return False 261 return False
238 262
263 # there might be other cases here, but it's safer to just
264 # return True if we can't guess any better
239 return True 265 return True
240 266
241 def __str__(self): 267 def __str__(self):
242 parent = "" 268 parent = ""
243 if self.parent: 269 if self.parent:
244 parent = ": child of 0x%x" % id(self.parent) 270 parent = ": child of 0x%x" % id(self.parent)
245 271
246 return "<MatchSet 0x%x %d tag templates, %d other templates, range=[%s:%s]%s>" % ( 272 return "<MatchSet 0x%x %s%d tag templates, %d other templates, range=[%s:%s]%s>" % (
247 id(self), len(self.state.tag_templates), len(self.other_templates), 273 id(self), self.not_empty and "" or "[empty] ",
274 len(self.state.tag_templates), len(self.other_templates),
248 self.min_index, self.max_index, 275 self.min_index, self.max_index,
249 parent) 276 parent)
Copyright (C) 2012-2017 Edgewall Software