align.py revision a27842ff 
1'''
2This module contains helper classes for alignment arithmetic and checks
3'''
4
5from fractions import gcd
6
7class Alignment(object):
8
9    def __init__(self, align=4, offset=0):
10        self.align = align
11        # normalize the offset (just in case)
12        self.offset = offset % align
13
14
15    def __eq__(self, other):
16        return self.align == other.align and self.offset == other.offset
17
18    def __str__(self):
19        return "(align=%d, offset=%d)" % (self.align, self.offset)
20
21    @staticmethod
22    def for_primitive_type(size):
23        # compute the required start_alignment based on the size of the type
24        if size % 8 == 0:
25            # do 8-byte primitives require 8-byte alignment in X11?
26            return Alignment(8,0)
27        elif size % 4 == 0:
28            return Alignment(4,0)
29        elif size % 2 == 0:
30            return Alignment(2,0)
31        else:
32            return Alignment(1,0)
33
34
35    def align_after_fixed_size(self, size):
36        new_offset = (self.offset + size) % self.align
37        return Alignment(self.align, new_offset)
38
39
40    def is_guaranteed_at(self, external_align):
41        '''
42        Assuming the given external_align, checks whether
43        self is fulfilled for all cases.
44        Returns True if yes, False otherwise.
45        '''
46        if self.align == 1 and self.offset == 0:
47            # alignment 1 with offset 0 is always fulfilled
48            return True
49
50        if external_align is None:
51            # there is no external align -> fail
52            return False
53
54        if external_align.align < self.align:
55            # the external align guarantees less alignment -> not guaranteed
56            return False
57
58        if external_align.align % self.align != 0:
59            # the external align cannot be divided by our align
60            # -> not guaranteed
61            # (this can only happen if there are alignments that are not
62            # a power of 2, which is highly discouraged. But better be
63            # safe and check for it)
64            return False
65
66        if external_align.offset % self.align != self.offset:
67            # offsets do not match
68            return False
69
70        return True
71
72
73    def combine_with(self, other):
74        # returns the alignment that is guaranteed when
75        # both, self or other, can happen
76        new_align = gcd(self.align, other.align)
77        new_offset_candidate1 = self.offset % new_align
78        new_offset_candidate2 = other.offset % new_align
79        if new_offset_candidate1 == new_offset_candidate2:
80            new_offset = new_offset_candidate1
81        else:
82            offset_diff = abs(new_offset_candidate2 - new_offset_candidate1)
83            new_align = gcd(new_align, offset_diff)
84            new_offset_candidate1 = self.offset % new_align
85            new_offset_candidate2 = other.offset % new_align
86            assert new_offset_candidate1 == new_offset_candidate2
87            new_offset = new_offset_candidate1
88        # return the result
89        return Alignment(new_align, new_offset)
90
91
92class AlignmentLog(object):
93
94    def __init__(self):
95        self.ok_list = []
96        self.fail_list = []
97        self.verbosity = 1
98
99    def __str__(self):
100        result = ""
101
102        # output the OK-list
103        for (align_before, field_name, type_obj, callstack, align_after) in self.ok_list:
104            stacksize = len(callstack)
105            indent = '  ' * stacksize
106            if self.ok_callstack_is_relevant(callstack):
107                if field_name is None or field_name == "":
108                    result += ("    %sok: %s:\n\t%sbefore: %s, after: %s\n"
109                        % (indent, str(type_obj), indent, str(align_before), str(align_after)))
110                else:
111                    result += ("    %sok: field \"%s\" in %s:\n\t%sbefore: %s, after: %s\n"
112                        % (indent, str(field_name), str(type_obj),
113                           indent, str(align_before), str(align_after)))
114                if self.verbosity >= 1:
115                    result += self.callstack_to_str(indent, callstack)
116
117        # output the fail-list
118        for (align_before, field_name, type_obj, callstack, reason) in self.fail_list:
119            stacksize = len(callstack)
120            indent = '  ' * stacksize
121            if field_name is None or field_name == "":
122                result += ("    %sfail: align %s is incompatible with\n\t%s%s\n\t%sReason: %s\n"
123                    % (indent, str(align_before), indent, str(type_obj), indent, reason))
124            else:
125                result += ("    %sfail: align %s is incompatible with\n\t%sfield \"%s\" in %s\n\t%sReason: %s\n"
126                    % (indent, str(align_before), indent, str(field_name), str(type_obj), indent, reason))
127
128            if self.verbosity >= 1:
129                result += self.callstack_to_str(indent, callstack)
130
131
132        return result
133
134
135    def callstack_to_str(self, indent, callstack):
136        result = "\t%scallstack: [\n" % indent
137        for stack_elem in callstack:
138            result += "\t  %s%s\n" % (indent, str(stack_elem))
139        result += "\t%s]\n" % indent
140        return result
141
142
143    def ok_callstack_is_relevant(self, ok_callstack):
144        # determine whether an ok callstack is relevant for logging
145        if self.verbosity >= 2:
146            return True
147
148        # empty callstacks are always relevant
149        if len(ok_callstack) == 0:
150            return True
151
152        # check whether the ok_callstack is a subset or equal to a fail_callstack
153        for (align_before, field_name, type_obj, fail_callstack, reason) in self.fail_list:
154            if len(ok_callstack) <= len(fail_callstack):
155                zipped = zip(ok_callstack, fail_callstack[:len(ok_callstack)])
156                is_subset = all([i == j for i, j in zipped])
157                if is_subset:
158                    return True
159
160        return False
161
162
163    def ok(self, align_before, field_name, type_obj, callstack, align_after):
164        self.ok_list.append((align_before, field_name, type_obj, callstack, align_after))
165
166    def fail(self, align_before, field_name, type_obj, callstack, reason):
167        self.fail_list.append((align_before, field_name, type_obj, callstack, reason))
168
169    def append(self, other):
170        self.ok_list.extend(other.ok_list)
171        self.fail_list.extend(other.fail_list)
172
173    def ok_count(self):
174        return len(self.ok_list)
175
176
177
178