Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(228)

Side by Side Diff: thirdparty/datastructures.py

Issue 7108020: Add automatic retry mechanism and LKGR support. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/tools/commit-queue
Patch Set: Created 9 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
1 # Source:
2 # https://code.djangoproject.com/svn/django/trunk/django/utils/datastructures.py @16292
3 # License:
4 # https://code.djangoproject.com/svn/django/trunk/LICENSE
5 # (BSD 3 cluases)
6
7 import copy
8 from types import GeneratorType
9
10 class MergeDict(object):
11 """
12 A simple class for creating new "virtual" dictionaries that actually look
13 up values in more than one dictionary, passed in the constructor.
14
15 If a key appears in more than one of the given dictionaries, only the
16 first occurrence will be used.
17 """
18 def __init__(self, *dicts):
19 self.dicts = dicts
20
21 def __getitem__(self, key):
22 for dict_ in self.dicts:
23 try:
24 return dict_[key]
25 except KeyError:
26 pass
27 raise KeyError
28
29 def __copy__(self):
30 return self.__class__(*self.dicts)
31
32 def get(self, key, default=None):
33 try:
34 return self[key]
35 except KeyError:
36 return default
37
38 def getlist(self, key):
39 for dict_ in self.dicts:
40 if key in dict_.keys():
41 return dict_.getlist(key)
42 return []
43
44 def iteritems(self):
45 seen = set()
46 for dict_ in self.dicts:
47 for item in dict_.iteritems():
48 k, v = item
49 if k in seen:
50 continue
51 seen.add(k)
52 yield item
53
54 def iterkeys(self):
55 for k, v in self.iteritems():
56 yield k
57
58 def itervalues(self):
59 for k, v in self.iteritems():
60 yield v
61
62 def items(self):
63 return list(self.iteritems())
64
65 def keys(self):
66 return list(self.iterkeys())
67
68 def values(self):
69 return list(self.itervalues())
70
71 def has_key(self, key):
72 for dict_ in self.dicts:
73 if key in dict_:
74 return True
75 return False
76
77 __contains__ = has_key
78 __iter__ = iterkeys
79
80 def copy(self):
81 """Returns a copy of this object."""
82 return self.__copy__()
83
84 def __str__(self):
85 '''
86 Returns something like
87
88 "{'key1': 'val1', 'key2': 'val2', 'key3': 'val3'}"
89
90 instead of the generic "<object meta-data>" inherited from object.
91 '''
92 return str(dict(self.items()))
93
94 def __repr__(self):
95 '''
96 Returns something like
97
98 MergeDict({'key1': 'val1', 'key2': 'val2'}, {'key3': 'val3'})
99
100 instead of generic "<object meta-data>" inherited from object.
101 '''
102 dictreprs = ', '.join(repr(d) for d in self.dicts)
103 return '%s(%s)' % (self.__class__.__name__, dictreprs)
104
105 class SortedDict(dict):
106 """
107 A dictionary that keeps its keys in the order in which they're inserted.
108 """
109 def __new__(cls, *args, **kwargs):
110 instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)
111 instance.keyOrder = []
112 return instance
113
114 def __init__(self, data=None):
115 if data is None:
116 data = {}
117 elif isinstance(data, GeneratorType):
118 # Unfortunately we need to be able to read a generator twice. Once
119 # to get the data into self with our super().__init__ call and a
120 # second time to setup keyOrder correctly
121 data = list(data)
122 super(SortedDict, self).__init__(data)
123 if isinstance(data, dict):
124 self.keyOrder = data.keys()
125 else:
126 self.keyOrder = []
127 seen = set()
128 for key, value in data:
129 if key not in seen:
130 self.keyOrder.append(key)
131 seen.add(key)
132
133 def __deepcopy__(self, memo):
134 return self.__class__([(key, copy.deepcopy(value, memo))
135 for key, value in self.iteritems()])
136
137 def __setitem__(self, key, value):
138 if key not in self:
139 self.keyOrder.append(key)
140 super(SortedDict, self).__setitem__(key, value)
141
142 def __delitem__(self, key):
143 super(SortedDict, self).__delitem__(key)
144 self.keyOrder.remove(key)
145
146 def __iter__(self):
147 return iter(self.keyOrder)
148
149 def pop(self, k, *args):
150 result = super(SortedDict, self).pop(k, *args)
151 try:
152 self.keyOrder.remove(k)
153 except ValueError:
154 # Key wasn't in the dictionary in the first place. No problem.
155 pass
156 return result
157
158 def popitem(self):
159 result = super(SortedDict, self).popitem()
160 self.keyOrder.remove(result[0])
161 return result
162
163 def items(self):
164 return zip(self.keyOrder, self.values())
165
166 def iteritems(self):
167 for key in self.keyOrder:
168 yield key, self[key]
169
170 def keys(self):
171 return self.keyOrder[:]
172
173 def iterkeys(self):
174 return iter(self.keyOrder)
175
176 def values(self):
177 return map(self.__getitem__, self.keyOrder)
178
179 def itervalues(self):
180 for key in self.keyOrder:
181 yield self[key]
182
183 def update(self, dict_):
184 for k, v in dict_.iteritems():
185 self[k] = v
186
187 def setdefault(self, key, default):
188 if key not in self:
189 self.keyOrder.append(key)
190 return super(SortedDict, self).setdefault(key, default)
191
192 def value_for_index(self, index):
193 """Returns the value of the item at the given zero-based index."""
194 return self[self.keyOrder[index]]
195
196 def insert(self, index, key, value):
197 """Inserts the key, value pair before the item with the given index."""
198 if key in self.keyOrder:
199 n = self.keyOrder.index(key)
200 del self.keyOrder[n]
201 if n < index:
202 index -= 1
203 self.keyOrder.insert(index, key)
204 super(SortedDict, self).__setitem__(key, value)
205
206 def copy(self):
207 """Returns a copy of this object."""
208 # This way of initializing the copy means it works for subclasses, too.
209 obj = self.__class__(self)
210 obj.keyOrder = self.keyOrder[:]
211 return obj
212
213 def __repr__(self):
214 """
215 Replaces the normal dict.__repr__ with a version that returns the keys
216 in their sorted order.
217 """
218 return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])
219
220 def clear(self):
221 super(SortedDict, self).clear()
222 self.keyOrder = []
223
224 class MultiValueDictKeyError(KeyError):
225 pass
226
227 class MultiValueDict(dict):
228 """
229 A subclass of dictionary customized to handle multiple values for the
230 same key.
231
232 >>> d = MultiValueDict({'name': ['Adrian', 'Simon'], 'position': ['Developer ']})
233 >>> d['name']
234 'Simon'
235 >>> d.getlist('name')
236 ['Adrian', 'Simon']
237 >>> d.getlist('doesnotexist')
238 []
239 >>> d.getlist('doesnotexist', ['Adrian', 'Simon'])
240 ['Adrian', 'Simon']
241 >>> d.get('lastname', 'nonexistent')
242 'nonexistent'
243 >>> d.setlist('lastname', ['Holovaty', 'Willison'])
244
245 This class exists to solve the irritating problem raised by cgi.parse_qs,
246 which returns a list for every key, even though most Web forms submit
247 single name-value pairs.
248 """
249 def __init__(self, key_to_list_mapping=()):
250 super(MultiValueDict, self).__init__(key_to_list_mapping)
251
252 def __repr__(self):
253 return "<%s: %s>" % (self.__class__.__name__,
254 super(MultiValueDict, self).__repr__())
255
256 def __getitem__(self, key):
257 """
258 Returns the last data value for this key, or [] if it's an empty list;
259 raises KeyError if not found.
260 """
261 try:
262 list_ = super(MultiValueDict, self).__getitem__(key)
263 except KeyError:
264 raise MultiValueDictKeyError("Key %r not found in %r" % (key, self))
265 try:
266 return list_[-1]
267 except IndexError:
268 return []
269
270 def __setitem__(self, key, value):
271 super(MultiValueDict, self).__setitem__(key, [value])
272
273 def __copy__(self):
274 return self.__class__([
275 (k, v[:])
276 for k, v in self.lists()
277 ])
278
279 def __deepcopy__(self, memo=None):
280 if memo is None:
281 memo = {}
282 result = self.__class__()
283 memo[id(self)] = result
284 for key, value in dict.items(self):
285 dict.__setitem__(result, copy.deepcopy(key, memo),
286 copy.deepcopy(value, memo))
287 return result
288
289 def __getstate__(self):
290 obj_dict = self.__dict__.copy()
291 obj_dict['_data'] = dict([(k, self.getlist(k)) for k in self])
292 return obj_dict
293
294 def __setstate__(self, obj_dict):
295 data = obj_dict.pop('_data', {})
296 for k, v in data.items():
297 self.setlist(k, v)
298 self.__dict__.update(obj_dict)
299
300 def get(self, key, default=None):
301 """
302 Returns the last data value for the passed key. If key doesn't exist
303 or value is an empty list, then default is returned.
304 """
305 try:
306 val = self[key]
307 except KeyError:
308 return default
309 if val == []:
310 return default
311 return val
312
313 def getlist(self, key, default=None):
314 """
315 Returns the list of values for the passed key. If key doesn't exist,
316 then a default value is returned.
317 """
318 try:
319 return super(MultiValueDict, self).__getitem__(key)
320 except KeyError:
321 if default is not None:
322 return default
323 return []
324
325 def setlist(self, key, list_):
326 super(MultiValueDict, self).__setitem__(key, list_)
327
328 def setdefault(self, key, default=None):
329 if key not in self:
330 self[key] = default
331 return self[key]
332
333 def setlistdefault(self, key, default_list=()):
334 if key not in self:
335 self.setlist(key, default_list)
336 return self.getlist(key)
337
338 def appendlist(self, key, value):
339 """Appends an item to the internal list associated with key."""
340 self.setlistdefault(key, [])
341 super(MultiValueDict, self).__setitem__(key, self.getlist(key) + [value] )
342
343 def items(self):
344 """
345 Returns a list of (key, value) pairs, where value is the last item in
346 the list associated with the key.
347 """
348 return [(key, self[key]) for key in self.keys()]
349
350 def iteritems(self):
351 """
352 Yields (key, value) pairs, where value is the last item in the list
353 associated with the key.
354 """
355 for key in self.keys():
356 yield (key, self[key])
357
358 def lists(self):
359 """Returns a list of (key, list) pairs."""
360 return super(MultiValueDict, self).items()
361
362 def iterlists(self):
363 """Yields (key, list) pairs."""
364 return super(MultiValueDict, self).iteritems()
365
366 def values(self):
367 """Returns a list of the last value on every key list."""
368 return [self[key] for key in self.keys()]
369
370 def itervalues(self):
371 """Yield the last value on every key list."""
372 for key in self.iterkeys():
373 yield self[key]
374
375 def copy(self):
376 """Returns a shallow copy of this object."""
377 return copy.copy(self)
378
379 def update(self, *args, **kwargs):
380 """
381 update() extends rather than replaces existing key lists.
382 Also accepts keyword args.
383 """
384 if len(args) > 1:
385 raise TypeError("update expected at most 1 arguments, got %d" % len( args))
386 if args:
387 other_dict = args[0]
388 if isinstance(other_dict, MultiValueDict):
389 for key, value_list in other_dict.lists():
390 self.setlistdefault(key, []).extend(value_list)
391 else:
392 try:
393 for key, value in other_dict.items():
394 self.setlistdefault(key, []).append(value)
395 except TypeError:
396 raise ValueError("MultiValueDict.update() takes either a Mul tiValueDict or dictionary")
397 for key, value in kwargs.iteritems():
398 self.setlistdefault(key, []).append(value)
399
400 class DotExpandedDict(dict):
401 """
402 A special dictionary constructor that takes a dictionary in which the keys
403 may contain dots to specify inner dictionaries. It's confusing, but this
404 example should make sense.
405
406 >>> d = DotExpandedDict({'person.1.firstname': ['Simon'], \
407 'person.1.lastname': ['Willison'], \
408 'person.2.firstname': ['Adrian'], \
409 'person.2.lastname': ['Holovaty']})
410 >>> d
411 {'person': {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {' lastname': ['Holovaty'], 'firstname': ['Adrian']}}}
412 >>> d['person']
413 {'1': {'lastname': ['Willison'], 'firstname': ['Simon']}, '2': {'lastname': ['Holovaty'], 'firstname': ['Adrian']}}
414 >>> d['person']['1']
415 {'lastname': ['Willison'], 'firstname': ['Simon']}
416
417 # Gotcha: Results are unpredictable if the dots are "uneven":
418 >>> DotExpandedDict({'c.1': 2, 'c.2': 3, 'c': 1})
419 {'c': 1}
420 """
421 def __init__(self, key_to_list_mapping):
422 for k, v in key_to_list_mapping.items():
423 current = self
424 bits = k.split('.')
425 for bit in bits[:-1]:
426 current = current.setdefault(bit, {})
427 # Now assign value to current position
428 try:
429 current[bits[-1]] = v
430 except TypeError: # Special-case if current isn't a dict.
431 current = {bits[-1]: v}
432
433 class ImmutableList(tuple):
434 """
435 A tuple-like object that raises useful errors when it is asked to mutate.
436
437 Example::
438
439 >>> a = ImmutableList(range(5), warning="You cannot mutate this.")
440 >>> a[3] = '4'
441 Traceback (most recent call last):
442 ...
443 AttributeError: You cannot mutate this.
444 """
445
446 def __new__(cls, *args, **kwargs):
447 if 'warning' in kwargs:
448 warning = kwargs['warning']
449 del kwargs['warning']
450 else:
451 warning = 'ImmutableList object is immutable.'
452 self = tuple.__new__(cls, *args, **kwargs)
453 self.warning = warning
454 return self
455
456 def complain(self, *wargs, **kwargs):
457 if isinstance(self.warning, Exception):
458 raise self.warning
459 else:
460 raise AttributeError(self.warning)
461
462 # All list mutation functions complain.
463 __delitem__ = complain
464 __delslice__ = complain
465 __iadd__ = complain
466 __imul__ = complain
467 __setitem__ = complain
468 __setslice__ = complain
469 append = complain
470 extend = complain
471 insert = complain
472 pop = complain
473 remove = complain
474 sort = complain
475 reverse = complain
476
477 class DictWrapper(dict):
478 """
479 Wraps accesses to a dictionary so that certain values (those starting with
480 the specified prefix) are passed through a function before being returned.
481 The prefix is removed before looking up the real value.
482
483 Used by the SQL construction code to ensure that values are correctly
484 quoted before being used.
485 """
486 def __init__(self, data, func, prefix):
487 super(DictWrapper, self).__init__(data)
488 self.func = func
489 self.prefix = prefix
490
491 def __getitem__(self, key):
492 """
493 Retrieves the real value after stripping the prefix string (if
494 present). If the prefix is present, pass the value through self.func
495 before returning, otherwise return the raw value.
496 """
497 if key.startswith(self.prefix):
498 use_func = True
499 key = key[len(self.prefix):]
500 else:
501 use_func = False
502 value = super(DictWrapper, self).__getitem__(key)
503 if use_func:
504 return self.func(value)
505 return value
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698