source: proto/parabix2/parabix2_compilable.py @ 1055

Last change on this file since 1055 was 775, checked in by cameron, 9 years ago

Nested version.

File size: 14.9 KB
Line 
1# -*- coding: utf-8 -*-
2#
3# parabix2_compilable.py
4#
5# Parallel XML Parsing with Bitstream Addition
6# - Complete prototype for all bitstream computations in Parabix2
7# - optimized for compilation
8#
9# Robert D. Cameron
10# July 29, 2010
11#
12
13#import bitutil
14
15
16
17def main(u8data):
18        # Transpose to parallel bit streams and prepare an EOF mask.
19        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
20
21        # Classify bytes for UTF-8 processing, whitespace and control
22        # processing and XML lexical analysis.
23
24        temp1 = (bit[0] | bit[1]);
25        temp2 = (bit[2] &~ bit[3]);
26        temp3 = (temp2 &~ temp1);
27        temp4 = (bit[5] &~ bit[4]);
28        temp5 = (bit[6] &~ bit[7]);
29        temp6 = (temp4 & temp5);
30        lex.RefStart = (temp3 & temp6);
31        temp7 = (bit[2] & bit[3]);
32        temp8 = (temp7 &~ temp1);
33        temp9 = (bit[4] &~ bit[5]);
34        temp10 = (bit[6] & bit[7]);
35        temp11 = (temp9 & temp10);
36        lex.Semicolon = (temp8 & temp11);
37        temp12 = (bit[4] & bit[5]);
38        temp13 = (bit[6] | bit[7]);
39        temp14 = (temp12 &~ temp13);
40        lex.LAngle = (temp8 & temp14);
41        temp15 = (temp12 & temp5);
42        lex.RAngle = (temp8 & temp15);
43        temp16 = (bit[1] &~ bit[0]);
44        temp17 = (bit[3] &~ bit[2]);
45        temp18 = (temp16 & temp17);
46        lex.LBracket = (temp18 & temp11);
47        temp19 = (bit[7] &~ bit[6]);
48        temp20 = (temp12 & temp19);
49        lex.RBracket = (temp18 & temp20);
50        temp21 = (bit[4] | bit[5]);
51        temp22 = (temp19 &~ temp21);
52        lex.Exclam = (temp3 & temp22);
53        temp23 = (temp12 & temp10);
54        lex.QMark = (temp8 & temp23);
55        lex.Hyphen = (temp3 & temp20);
56        lex.Equals = (temp8 & temp20);
57        temp24 = (temp4 & temp10);
58        lex.SQuote = (temp3 & temp24);
59        temp25 = (temp5 &~ temp21);
60        lex.DQuote = (temp3 & temp25);
61        lex.Slash = (temp3 & temp23);
62        temp26 = (temp10 &~ temp21);
63        lex.Hash = (temp3 & temp26);
64        temp27 = (temp16 & temp7);
65        temp28 = (temp9 &~ temp13);
66        lex.x = (temp27 & temp28);
67        temp29 = (temp9 & temp5);
68        lex.Colon = (temp8 & temp29);
69        temp30 = (temp18 & temp23);
70        temp31 = (temp30 | lex.Colon);
71        temp32 = (temp16 &~ bit[2]);
72        temp33 = (bit[5] | temp10);
73        temp34 = (bit[4] & temp33);
74        temp35 = (~temp34);
75        temp36 = (temp21 | temp13);
76        temp37 = ((bit[3] & temp35)|(~(bit[3]) & temp36));
77        temp38 = (temp32 & temp37);
78        temp39 = (temp31 | temp38);
79        temp40 = (temp16 & bit[2]);
80        temp41 = (temp40 & temp37);
81        lex.ASCII_name_start = (temp39 | temp41);
82        temp42 = (temp30 | lex.Hyphen);
83        temp43 = (temp3 & temp15);
84        temp44 = (temp42 | temp43);
85        temp45 = (temp8 &~ temp34);
86        temp46 = (temp44 | temp45);
87        temp47 = (temp46 | temp38);
88        lex.ASCII_name_char = (temp47 | temp41);
89        lex.NameScan = (lex.ASCII_name_char | bit[0]);
90        temp48 = (temp1 | bit[2]);
91        control.x00_x1F = (~temp48);
92        temp49 = (bit[2] | bit[3]);
93        temp50 = (temp1 | temp49);
94        control.CR = (temp20 &~ temp50);
95        control.LF = (temp29 &~ temp50);
96        temp51 = (temp9 & temp19);
97        control.HT = (temp51 &~ temp50);
98        control.SP = (temp3 &~ temp36);
99        temp52 = (temp20 | temp29);
100        temp53 = (temp52 | temp51);
101        temp54 = (temp53 &~ temp50);
102        lex.WS = (temp54 | control.SP);
103        temp55 = (bit[5] | bit[6]);
104        temp56 = (bit[4] & temp55);
105        lex.Digit = (temp8 &~ temp56);
106        temp57 = (temp16 &~ temp49);
107        temp58 = (temp57 &~ bit[4]);
108        temp59 = (~temp10);
109        temp60 = ((bit[5] & temp59)|(~(bit[5]) & temp13));
110        temp61 = (temp58 & temp60);
111        temp62 = (lex.Digit | temp61);
112        temp63 = (temp16 & temp2);
113        temp64 = (temp63 &~ bit[4]);
114        temp65 = (temp64 & temp60);
115        lex.Hex = (temp62 | temp65);
116
117
118        # Check for illegal control characters
119        xmlchar_error = (control.x00_x1F &~ lex.WS & EOF_mask)
120
121
122        u8.unibyte = (~bit[0]);
123        u8.suffix = 0
124        u8.error = 0
125        FFFE_FFFF = 0
126
127        if bit[0]:
128                u8.prefix = (bit[0] & bit[1]);
129                u8.prefix2 = (u8.prefix &~ bit[2]);
130                u8.prefix3 = (u8.prefix & temp2);
131                u8.prefix4 = (u8.prefix & temp7);
132                u8.suffix = (bit[0] &~ bit[1]);
133                temp66 = (u8.prefix &~ temp49);
134                temp67 = (temp21 | bit[6]);
135                temp68 = (temp66 &~ temp67);
136                temp69 = (bit[5] & temp13);
137                temp70 = (bit[4] | temp69);
138                temp71 = (u8.prefix4 & temp70);
139                u8.badprefix = (temp68 | temp71);
140                xE0 = (u8.prefix3 &~ temp36);
141                xED = (u8.prefix3 & temp20);
142                xF0 = (u8.prefix4 &~ temp36);
143                temp72 = (temp4 &~ temp13);
144                xF4 = (u8.prefix4 & temp72);
145                u8.xA0_xBF = (u8.suffix & bit[2]);
146                u8.x80_x9F = (u8.suffix &~ bit[2]);
147                u8.x90_xBF = (u8.suffix & temp49);
148                u8.x80_x8F = (u8.suffix &~ temp49);
149                xEF = (u8.prefix3 & temp23);
150                temp73 = (u8.suffix & temp7);
151                u8.xBF = (temp73 & temp23);
152                u8.xBE = (temp73 & temp15);
153                u8.xE0_scope = bitutil.Advance(xE0);
154                u8.xED_scope = bitutil.Advance(xED);
155                u8.xF0_scope = bitutil.Advance(xF0);
156                u8.xF4_scope = bitutil.Advance(xF4);
157                u8.xEF_scope = bitutil.Advance(xEF);
158                u8.scope22 = bitutil.Advance(u8.prefix2)
159                u8.scope32 = bitutil.Advance(u8.prefix3)
160                u8.scope33 = bitutil.Advance(u8.scope32)
161                u8.scope42 = bitutil.Advance(u8.prefix4)
162                u8.scope43 = bitutil.Advance(u8.scope42)
163                u8.scope44 = bitutil.Advance(u8.scope43)
164
165                u8lastscope = u8.scope22 | u8.scope33 | u8.scope44
166                u8anyscope = u8lastscope | u8.scope32 | u8.scope42 | u8.scope43
167               
168                u8error1 = u8.xE0_scope & u8.x80_x9F
169                u8error2 = u8.xED_scope & u8.xA0_xBF
170                u8error3 = u8.xF0_scope & u8.x80_x8F
171                u8error4 = u8.xF4_scope & u8.x90_xBF
172       
173                u8mismatch = u8anyscope ^ u8.suffix
174
175                u8.error = u8.badprefix | u8error1 | u8error2 | u8error3 | u8error4 | u8mismatch
176
177                EF_BF_pending = bitutil.Advance(u8.xEF_scope & u8.xBF)
178
179                FFFE_FFFF = (EF_BF_pending & (u8.xBE | u8.xBF))
180
181        xmlchar_error |= FFFE_FFFF
182
183        lex.LAngle_scope = bitutil.Advance(lex.LAngle)
184        lex.Hyphen_scope = bitutil.Advance(lex.Hyphen)
185        lex.QMark_scope = bitutil.Advance(lex.QMark)
186
187        lex.CD_end = 0
188        if lex.RBracket:
189                lex.RBracket_scope = bitutil.Advance(lex.RBracket)
190                lex.CD_end = bitutil.Advance(lex.RBracket_scope & lex.RBracket) & lex.RAngle
191
192        # Compute XML multilterals such as <?, </, --, ]]>.
193        #lex = add_multiliterals(lex)
194        lex.PI_start = lex.LAngle_scope & lex.QMark
195        lex.CtCD_start = lex.LAngle_scope & lex.Exclam
196        lex.CtCDPI_start = lex.PI_start | lex.CtCD_start
197        lex.EndTag_start = lex.LAngle_scope & lex.Slash
198
199        #if lex.CtCDPI_start:
200        lex.DoubleHyphen = lex.Hyphen_scope & lex.Hyphen
201        lex.PI_end = lex.QMark_scope & lex.RAngle
202
203       
204        # THE FOLLOWING FUNCTIONAL CALL IS MANUALLY INLINED
205        # Parse all comments, CDATA sections and processing instructions.
206        #markup1 = parse_CtCDPI(lex, EOF_mask)
207        #CT_callouts = CtCDPI_callouts()
208        CT_callouts.PI_name = 0
209        PI_starts = 0
210        PI_ends = 0
211        Ct_starts = 0
212        Ct_ends = 0
213        CD_starts = 0
214        CD_ends = 0
215        CtCDPI_starts = 0
216        PI_namestarts = 0
217        PI_name_ends = 0
218
219        # Scanning streams
220        CtCDPI_scan = ~lex.CtCDPI_start & EOF_mask
221        Ct_end_scan = ~lex.DoubleHyphen & EOF_mask
222        CD_end_scan = ~lex.CD_end & EOF_mask
223        PI_end_scan = ~lex.PI_end & EOF_mask
224        #
225        # Initiate the scan
226        CtCDPI_Cursor = 1
227        CtCDPI_Cursor = bitutil.ScanThru(CtCDPI_Cursor, CtCDPI_scan)
228        CtCDPI_Cursor &= EOF_mask
229        while CtCDPI_Cursor:
230                CtCDPI_starts |= CtCDPI_Cursor
231                PI_Cursor = CtCDPI_Cursor & lex.PI_start
232                CD_Ct_Cursor = bitutil.Advance(CtCDPI_Cursor & ~PI_Cursor)
233                CD_Cursor = CD_Ct_Cursor & lex.LBracket
234                #Ct_Cursor = bitutil.Advance(CD_Ct_Cursor & lex.Hyphen)
235                Ct_Cursor = CD_Ct_Cursor & lex.Hyphen
236                PI_starts |= PI_Cursor
237                CD_starts |= CD_Cursor
238                Ct_starts |= Ct_Cursor
239                Ct_Cursor = bitutil.Advance(Ct_Cursor) 
240                Ct_errors |= Ct_Cursor & ~ lex.Hyphen
241                Ct_Cursor = bitutil.Advance(Ct_Cursor)
242                Ct_end_scan |= Ct_Cursor
243                #PI_Cursor = bitutil.ScanThru(PI_Cursor, PI_end_scan)
244                PI_Cursor = bitutil.Advance(PI_Cursor)
245                PI_namestarts |= PI_Cursor
246                PI_name_end = bitutil.ScanThru(PI_Cursor, lex.NameScan)
247                PI_name_ends |= PI_name_end
248                CT_callouts.PI_name |= PI_name_end - PI_Cursor
249                PI_Cursor = bitutil.ScanThru(PI_name_end, PI_end_scan)
250                CD_Cursor = bitutil.ScanThru(CD_Cursor, CD_end_scan)
251                Ct_Cursor = bitutil.Advance(bitutil.ScanThru(Ct_Cursor, Ct_end_scan))
252                PI_ends |= PI_Cursor
253                CD_ends |= CD_Cursor
254                Ct_ends |= Ct_Cursor
255                CtCDPI_Cursor = PI_Cursor | CD_Cursor | Ct_Cursor
256                CtCDPI_Cursor = bitutil.ScanThru(CtCDPI_Cursor, CtCDPI_scan)
257                CtCDPI_Cursor &= EOF_mask
258       
259                CT_callouts.CtCDPI_mask = bitutil.Advance(CD_ends | Ct_ends | PI_ends) - CtCDPI_starts
260                #CT_callouts.error = Ct_ends & ~lex.RAngle | Ct_starts & ~ lex.Hyphen
261                CT_callouts.error = Ct_errors | Ct_ends & ~lex.RAngle
262                CT_callouts.error |= bitutil.Advance(PI_name_ends & ~ lex.WS) & ~ lex.PI_end
263                CT_callouts.error |= PI_namestarts & PI_name_ends
264                # If any of the Comment, CDATA or PI markups are unterminated, it is an error.
265                CT_callouts.error |= CT_callouts.CtCDPI_mask &~ EOF_mask
266               
267        Misc_mask = (lex.WS | lex.LAngle | (bitutil.Advance(Ct_ends | PI_ends) - (Ct_starts | PI_starts)) | CtCDPI_starts) & EOF_mask
268        # End of loop: no remaining CtCDPI_Cursor
269       
270        ########## END OF MANUAL INLINING
271       
272        # THE FOLLOWING FUNCTIONAL CALL IS MANUALLY INLINED
273        # All remaining "<" must be tag start characters; parse tags.
274        #tags = parse_tags(lex, CT_callouts.CtCDPI_mask, EOF_mask)
275
276        #callouts = tag_callouts()
277       
278        # Delimiters for scans.
279        DQuoteScan = ~(lex.DQuote | lex.LAngle) & EOF_mask
280        SQuoteScan = ~(lex.SQuote | lex.LAngle) & EOF_mask
281        AttListDelim = lex.Slash | lex.RAngle
282       
283        # Start the parallel parsing by inspecting the character
284        # after the opening "<" of a tag.
285        LAngleFollow = lex.LAngle_scope &~ CT_callouts.CtCDPI_mask
286        ElemNamePositions = LAngleFollow & ~lex.Slash
287        EndTagSeconds = LAngleFollow & lex.Slash
288       
289        # Start Tag/Empty Element Tag Parsing
290
291        # Advance all cursors by scanning through the tag name.
292        ElemNameFollows = bitutil.ScanThru(ElemNamePositions, lex.NameScan)
293        # Must have at least one name character for a legal start tag.
294        # Mark any occurrences of null names as errors.
295        ParseError = ElemNamePositions & ElemNameFollows
296        callouts.ElemNames = ElemNameFollows - ElemNamePositions
297       
298        # Initialize the accumulators for attribute name and value positions.
299        AttNameStarts = 0 
300        AttNameFollows = 0
301        EqToCheck = 0
302        AttValStarts = 0
303        AttValEnds = 0
304        AttValFollows = 0
305
306        # After the element name, there may or may not be an attlist.
307        AfterWS = bitutil.ScanThru(ElemNameFollows, lex.WS)
308        AttListEnd = AfterWS & AttListDelim
309        AttNameStart = AfterWS & ~AttListDelim
310        # At least one WS character is required between ElemNames and AttNames.
311        ParseError |= ElemNameFollows & AttNameStart
312
313        #
314        # The following loop iterates through attributes within a start tag.
315        # Because all start tags are processed in parallel, the number of
316        # iterations is the maximum number of attributes found in any one
317        # start tag, plus one.
318        while AttNameStart:
319                AttNameStarts |= AttNameStart
320                AttNameFollow = bitutil.ScanThru(AttNameStart, lex.NameScan)
321                AttNameFollows |= AttNameFollow
322                # Scan through WS to the expected '=' delimiter.
323                EqExpected = bitutil.ScanThru(AttNameFollow, lex.WS)
324                EqToCheck |= EqExpected
325                AttValPos = bitutil.ScanThru(EqExpected, EqExpected | lex.WS)
326                AttValStarts |= AttValPos
327                DQuoteAttVal = AttValPos & lex.DQuote
328                SQuoteAttVal = AttValPos & lex.SQuote
329                DQuoteAttEnd = bitutil.ScanThru(DQuoteAttVal, DQuoteAttVal | DQuoteScan)
330                SQuoteAttEnd = bitutil.ScanThru(SQuoteAttVal, SQuoteAttVal | SQuoteScan)
331                AttValEnd = DQuoteAttEnd | SQuoteAttEnd
332                AttValEnds |= AttValEnd
333                AttValFollow = bitutil.Advance(AttValEnd)
334                AttValFollows |= AttValFollow
335                AfterWS = bitutil.ScanThru(AttValFollow, lex.WS)
336                AttListEnd |= AfterWS & AttListDelim
337                AttNameStart = AfterWS & ~AttListDelim
338
339        # No more attribute values to process when AttNameStart == 0.
340        # Not needed for xmlwf
341        callouts.AttNames = AttNameFollows - AttNameStarts
342        callouts.AttVals = AttValFollows - AttValStarts
343        STagEnds = AttListEnd & lex.RAngle
344        # Mark any "/" characters found as the ends of empty element tags.
345        callouts.EmptyTagMarks = bitutil.Advance(AttListEnd & lex.Slash)
346        callouts.Tags = (STagEnds | callouts.EmptyTagMarks) - ElemNamePositions
347       
348        # Check for errors.
349        ParseError |= AttValFollows & AttNameStarts # No intervening WS.
350        ParseError |= AttNameStarts & AttNameFollows # Null AttName
351        ParseError |= EqToCheck & ~lex.Equals # = not found where expected.
352        ParseError |= AttValStarts & ~ (lex.DQuote | lex.SQuote)
353        ParseError |= AttValEnds & ~ (lex.DQuote | lex.SQuote)
354        ParseError |= callouts.EmptyTagMarks & ~lex.RAngle
355
356        # End Tag Parsing
357        EndTagEnds = bitutil.ScanThru(bitutil.ScanThru(EndTagSeconds, EndTagSeconds | lex.NameScan), lex.WS)
358        ParseError |= EndTagEnds & ~lex.RAngle
359        # Not needed for xmlwf
360        #callouts.EndTags = EndTagEnds - EndTagSeconds
361        callouts.error = ParseError
362        ########## END OF MANUAL INLINING
363
364
365
366
367        # All remaining "&" must be reference start characters; parse them.
368        # INLINED: refs = parse_refs(lex, CT_callouts.CtCDPI_mask)
369        refs.GenRefs = 0
370        refs.error = 0
371        Ref2 = 0
372        GenRef2 = 0
373        DecRef3 = 0
374        HexRef4 = 0
375        Ref1 = lex.RefStart &~ CT_callouts.CtCDPI_mask
376        if Ref1:
377                Ref2 = bitutil.Advance(Ref1)
378                NumRef2 = Ref2 & lex.Hash
379                GenRef2 = Ref2 &~ lex.Hash
380                NumRef3 = bitutil.Advance(NumRef2)
381                HexRef3 = NumRef3 & lex.x
382                DecRef3 = NumRef3 &~ lex.x
383                HexRef4 = bitutil.Advance(HexRef3) 
384                GenRefEnds = bitutil.ScanThru(GenRef2, lex.NameScan)
385                DecRefEnds = bitutil.ScanThru(DecRef3, lex.Digit)
386                HexRefEnds = bitutil.ScanThru(HexRef4, lex.Hex)
387                # Error checks
388                # At least one digit required for DecRef, one hex digit for HexRef.
389                error1 = DecRef3 &~ lex.Digit
390                error2 = HexRef4 &~ lex.Hex
391                # Semicolon terminator required (also covers unterminated at EOF).
392                error3 = (GenRefEnds | DecRefEnds | HexRefEnds) &~ lex.Semicolon
393                refs.GenRefs = GenRefEnds - GenRef2
394                #refs.DecRefs = DecRefEnds - DecRef3
395                #refs.HexRefs = HexRefEnds - HexRef4
396                # Mark references for deletion, but leave the trailing semicolon as
397                # the point for insertion of the "expansion" text (most often a
398                # single character).
399
400                refs.error = error1 | error2 | error3
401
402
403        # Ensure that no occurrence of ]]> occurs outside of markup.
404        #CD_end_error = validate_no_CD_end(lex, CT_callouts, callouts)
405        CD_end_error = lex.CD_end & ~(CT_callouts.CtCDPI_mask | callouts.Tags)
406       
407
408       
409        #name and name start checking streams
410        qname_stream =  callouts.ElemNames | callouts.AttNames
411        ncname_stream = CT_callouts.PI_name | refs.GenRefs
412        name_stream = qname_stream | ncname_stream
413        name_start = name_stream &~ bitutil.Advance(name_stream)
414        name_start_check = name_start & ~lex.ASCII_name_start
415        name_check = (name_stream &~ name_start) & ~lex.ASCII_name_char & ~u8.suffix
416       
417        #namespace validation
418        name_cursor = name_stream & ~bitutil.Advance(name_stream)
419        void_prefix_err = name_cursor & lex.Colon
420        namespace_sep = bitutil.ScanThru(name_cursor, lex.NameScan &~ lex.Colon) & lex.Colon
421        local_part_start = bitutil.Advance(namespace_sep)
422        local_part_err = local_part_start &~ lex.NameScan
423        colon2_err = bitutil.ScanThru(local_part_start, lex.NameScan &~ lex.Colon) & lex.Colon
424        ncname_err = ncname_stream & lex.Colon
425        namespace_error = void_prefix_err | local_part_err | colon2_err | ncname_err
426       
427       
428        # Consolidate and check for errors
429        error_mask = u8.error | xmlchar_error | CT_callouts.error | callouts.error | CD_end_error | refs.error | namespace_error
430
431
432        #return (CT_callouts, callouts, refs, u16hi, u16lo, delmask, error, lex, u16delmask, EOF_mask)
433        tag_marks = callouts.EmptyTagMarks | LAngleFollow | AttNameStarts
434        NameFollows = ElemNameFollows | AttNameFollows
435        AttRef = callouts.AttVals & Ref2
436        return (CT_callouts, callouts, refs, error, lex, EOF_mask, name_check, name_start_check, control, tag_marks, NameFollows, CD_starts, GenRef2, DecRef3, HexRef4, AttRef, Misc_mask)
437
438       
Note: See TracBrowser for help on using the repository browser.