source: proto/parabix2/parabix2.py @ 441

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

Add shift 1 optimization

File size: 29.7 KB
Line 
1#
2# parabix2.py
3#
4# Parallel XML Parsing with Bitstream Addition
5# - Complete prototype for all bitstream computations in Parabix2
6#
7# Robert D. Cameron
8# August 20, 2009
9#
10#----------------------------------------------------------------------------
11#
12# We use python's unlimited precision integers for unbounded bit streams.
13# This permits simple logical operations on the entire stream.
14# Assumption: bitstreams are little-endian (e.g., as on x86).
15#
16#----------------------------------------------------------------------------
17#
18
19
20import bitutil
21
22import byteclass
23
24import u8u16
25
26import sys
27
28
29def validate_xmlchar(u8, control, lex, EOF_mask):
30        r"""Compute an error stream marking characters illegal in XML:
31        (1) Control characters in the range 0x00-0x1F except HT, LF, CR
32        (2) OxFFFF and OxFFFE, having UTF-8 encodings 0xEF 0xBF 0XBF and 0xEF 0xBF 0xBE.
33
34        >>> demo_validate_xmlchar('plaintext (good: \x09) (bad: \x03) (bad \xEF\xBF\xBF) (good \xEF\xBF\xBC)')
35        input high nybbles: 7666676772266663202226663202226662ebb22266662ebb2
36        input low nybbles : 0c19e4584087ff4a09908214a039082140fff9087ff40ffc9
37        illegal XML chars : __________________________1_________1_____________
38"""
39        EF_BF_pending = bitutil.Advance(u8.xEF_scope & u8.xBF)
40        return (EF_BF_pending & (u8.xBE | u8.xBF)) | (control.x00_x1F &~ lex.WS & EOF_mask)
41
42
43def demo_validate_xmlchar(u8data):
44        lgth = len(u8data)
45        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
46        (u8, control, lex) = byteclass.classify_bytes(bit)
47        bitutil.print_aligned_streams([('input high nybbles', bitutil.high_nybble_stream(u8data)), 
48                              ('input low nybbles', bitutil.low_nybble_stream(u8data)),
49                              ('illegal XML chars', bitutil.bitstream2string(validate_xmlchar(u8, control, lex, EOF_mask), lgth+1))])
50
51def normalize_line_breaks(control, bit):
52        r"""Convert CRs to LFs and mark CRLF occurrences for deletion.
53
54        >>> demo_line_breaks('ab \r\n  cd \r  ef \r ')
55        input high nybbles: 662002266202266202
56        input low nybbles : 120da00340d00560d0
57        CR                : ___1______1_____1_
58        LF                : ____1_____________
59        CRLF              : ____1_____________
60"""
61        control.CRLF = control.CR_scope & control.LF
62        # Convert CRs to LFs (flip bits 5, 6 and 7 with xor).
63        bit[5] ^= control.CR
64        bit[6] ^= control.CR
65        bit[7] ^= control.CR
66        return (control, bit)
67
68def demo_line_breaks(u8data):
69        lgth = len(u8data)
70        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
71        (u8, control, lex) = byteclass.classify_bytes(bit)
72        (control, bit) = normalize_line_breaks(control, bit)
73        bitutil.print_aligned_u8_byte_streams([('input high nybbles', bitutil.high_nybble_stream(u8data)), 
74                              ('input low nybbles', bitutil.low_nybble_stream(u8data)),
75                              ('CR', bitutil.bitstream2string(control.CR, lgth)),
76                              ('LF', bitutil.bitstream2string(control.LF, lgth)),
77                              ('CRLF', bitutil.bitstream2string(control.CRLF, lgth))])
78
79
80
81
82
83def add_multiliterals(lex):
84        """Extend the byte-based lexical item streams for some important
85        multibyte literals.
86       
87        >>> demo_multiliterals("  <?php?>  <!--  -->  <![CDATA[  ]]> ")
88        input data  :   <?php?>  <!--  -->  <![CDATA[  ]]>
89        PI_start    : ___1_________________________________
90        CtCD_start  : ____________1__________1_____________
91        EndTag_start: _____________________________________
92        CD_end      : ___________________________________1_
93        DoubleHyphen: ______________1___1__________________
94        PI_end      : ________1____________________________
95        """
96
97        lex.PI_start = lex.LAngle_scope & lex.QMark
98        lex.CtCD_start = lex.LAngle_scope & lex.Exclam
99        lex.EndTag_start = lex.LAngle_scope & lex.Slash
100        lex.CD_end = bitutil.Advance(lex.RBracket_scope & lex.RBracket) & lex.RAngle
101        lex.DoubleHyphen = lex.Hyphen_scope & lex.Hyphen
102        lex.PI_end = lex.QMark_scope & lex.RAngle
103        return lex
104
105def demo_multiliterals(u8data):
106        lgth = len(u8data)
107        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
108        (u8, control, lex) = byteclass.classify_bytes(bit)
109        lex = add_multiliterals(lex)
110        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
111                              ('PI_start', bitutil.bitstream2string(lex.PI_start, lgth)),
112                              ('CtCD_start', bitutil.bitstream2string(lex.CtCD_start, lgth)),
113                              ('EndTag_start', bitutil.bitstream2string(lex.EndTag_start, lgth)),
114                              ('CD_end', bitutil.bitstream2string(lex.CD_end, lgth)),
115                              ('DoubleHyphen', bitutil.bitstream2string(lex.DoubleHyphen, lgth)),
116                              ('PI_end', bitutil.bitstream2string(lex.PI_end, lgth))])
117
118class CtCDPI_callouts:
119        CD_span = 0
120        Ct_span = 0
121        PI_mask = 0
122        CtCDPI_mask = 0
123        error = 0
124       
125def parse_CtCDPI(lex, EOF_mask):
126        """Parse all comments, CDATA sections and processing instructions.
127       
128        Return bitstreams marking the extent of these markup items,
129        excluding initial and final bracketting.
130       
131        >>> demo_CtCDPI(' <?php?>  <!-- example -->  <![CDATA[  shift: a<<1 ]]> ')
132        input data :  <?php?>  <!-- example -->  <![CDATA[  shift: a<<1 ]]>
133        CD_span    : ______________________________11111111111111111111111__
134        Ct_span    : _____________111111111111______________________________
135        PI_span    : __11111________________________________________________
136        CtCDPI_mask: __111111___111111111111111___1111111111111111111111111_
137        error      : ________________________________________________________
138       
139        Comments are terminated by double-hyphen; immediately require closing ">".
140       
141        >>> demo_CtCDPI(' <!--  <?php?>  --   <!-- -->')
142        input data :  <!--  <?php?>  --   <!-- -->
143        CD_span    : _____________________________
144        Ct_span    : ____11111111111111______1111_
145        PI_span    : _____________________________
146        CtCDPI_mask: __11111111111111111___1111111
147        error      : __________________1___________
148
149
150
151"""
152        callouts = CtCDPI_callouts()
153        PI_starts = 0
154        PI_ends = 0
155        Ct_starts = 0
156        Ct_ends = 0
157        CD_starts = 0
158        CD_ends = 0
159        CtCDPI_starts = 0
160        # Scanning streams
161        CtCDPI_scan = ~(lex.CtCD_start | lex.PI_start) & EOF_mask
162        Ct_end_scan = ~lex.DoubleHyphen & EOF_mask
163        CD_end_scan = ~lex.CD_end & EOF_mask
164        PI_end_scan = ~lex.PI_end & EOF_mask
165        #
166        # Initiate the scan
167        CtCDPI_Cursor = 1
168        CtCDPI_Cursor = bitutil.ScanThru(CtCDPI_Cursor, CtCDPI_scan)
169        CtCDPI_Cursor &= EOF_mask
170        while CtCDPI_Cursor:
171                CtCDPI_starts |= CtCDPI_Cursor
172                PI_Cursor = CtCDPI_Cursor & lex.PI_start
173                CD_Ct_Cursor = bitutil.Advance(CtCDPI_Cursor & ~PI_Cursor)
174                CD_Cursor = CD_Ct_Cursor & lex.LBracket
175                Ct_Cursor = bitutil.Advance(CD_Ct_Cursor & lex.Hyphen) 
176                PI_starts |= PI_Cursor
177                CD_starts |= CD_Cursor
178                Ct_starts |= Ct_Cursor
179                Ct_Cursor = bitutil.Advance(Ct_Cursor)
180                Ct_end_scan |= Ct_Cursor
181                PI_Cursor = bitutil.ScanThru(PI_Cursor, PI_end_scan)
182                CD_Cursor = bitutil.ScanThru(CD_Cursor, CD_end_scan)
183                Ct_Cursor = bitutil.Advance(bitutil.ScanThru(Ct_Cursor, Ct_end_scan))
184                PI_ends |= PI_Cursor
185                CD_ends |= CD_Cursor
186                Ct_ends |= Ct_Cursor
187                CtCDPI_Cursor = PI_Cursor | CD_Cursor | Ct_Cursor
188                CtCDPI_Cursor = bitutil.ScanThru(CtCDPI_Cursor, CtCDPI_scan)
189                CtCDPI_Cursor &= EOF_mask
190        # End of loop: no remaining CtCDPI_Cursor
191        callouts.CD_span = CD_ends - CD_starts
192        callouts.Ct_span = Ct_ends - Ct_starts
193        callouts.PI_span = PI_ends - PI_starts
194       
195        callouts.CtCDPI_mask |= bitutil.Advance(CD_ends | Ct_ends | PI_ends) - CtCDPI_starts
196        callouts.error = Ct_ends & ~lex.RAngle | Ct_starts & ~ lex.Hyphen
197        # If any of the Comment, CDATA or PI markups are unterminated, it is an error.
198        callouts.error |= callouts.CtCDPI_mask &~ EOF_mask
199        return callouts
200
201def demo_CtCDPI(u8data):
202        lgth = len(u8data)
203        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
204        (u8, control, lex) = byteclass.classify_bytes(bit)
205        lex = add_multiliterals(lex)
206        markup = parse_CtCDPI(lex, EOF_mask)
207        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
208                              ('CD_span', bitutil.bitstream2string(markup.CD_span, lgth)),
209                              ('Ct_span', bitutil.bitstream2string(markup.Ct_span, lgth)),
210                              ('PI_span', bitutil.bitstream2string(markup.PI_span, lgth)),
211                              ('CtCDPI_mask', bitutil.bitstream2string(markup.CtCDPI_mask, lgth)),
212                              ('error', bitutil.bitstream2string(markup.error, lgth+1))])
213
214
215class ref_callouts:
216        GenRefs = 0
217        DecRefs = 0
218        HexRefs = 0
219        delmask = 0
220        error = 0
221
222def parse_refs(lex, CtCDPI_mask):
223        """Parse and call out all general and character references.
224        Mark all but the closing semicolon for deletion.
225       
226        >>> demo_refs(" &gt;  &#13;  &#x0a;  ")
227        input data       :  &gt;  &#13;  &#x0a; 
228        entity refs      : __11__________________
229        decimal char refs: _________11___________
230        hex char refs    : _________________11___
231        ref delmask      : _111___1111___11111___
232        errors           : _______________________
233
234        Empty numeric references are reported as errors.
235        >>> demo_refs(" &#;       &#x; ")
236        input data       :  &#;       &#x;
237        entity refs      : ________________
238        decimal char refs: ________________
239        hex char refs    : ________________
240        ref delmask      : _11________111__
241        errors           : ___1__________1__
242
243        Improperly terminated or unterminated references (lacking ";") are also errors.
244        >>> demo_refs("  &gt:  &#456a;  &#xab:  &unterminated")
245        input data       :   &gt:  &#456a;  &#xab:  &unterminated
246        entity refs      : ___111____________________111111111111
247        decimal char refs: __________111_________________________
248        hex char refs    : ____________________11________________
249        ref delmask      : __1111__11111____11111___1111111111111
250        errors           : ______1______1________1_______________1
251"""
252        CallOuts = ref_callouts()
253        Ref2 = lex.RefStart_scope &~ CtCDPI_mask
254        NumRef2 = Ref2 & lex.Hash
255        GenRef2 = Ref2 &~ lex.Hash
256        NumRef3 = bitutil.Advance(NumRef2)
257        HexRef3 = NumRef3 & lex.x
258        DecRef3 = NumRef3 &~ lex.x
259        HexRef4 = bitutil.Advance(HexRef3) 
260        GenRefEnds = bitutil.ScanThru(GenRef2, lex.NameScan)
261        DecRefEnds = bitutil.ScanThru(DecRef3, lex.Digit)
262        HexRefEnds = bitutil.ScanThru(HexRef4, lex.Hex)
263        # Error checks
264        # At least one digit required for DecRef, one hex digit for HexRef.
265        Error = DecRef3 &~ lex.Digit
266        Error |= HexRef4 &~ lex.Hex
267        # Semicolon terminator required (also covers unterminated at EOF).
268        Error |= (GenRefEnds | DecRefEnds | HexRefEnds) &~ lex.Semicolon
269        CallOuts.GenRefs = GenRefEnds - GenRef2
270        CallOuts.DecRefs = DecRefEnds - DecRef3
271        CallOuts.HexRefs = HexRefEnds - HexRef4
272        # Mark references for deletion, but leave the trailing semicolon as
273        # the point for insertion of the "expansion" text (most often a
274        # single character).
275        CallOuts.delmask = (GenRefEnds | DecRefEnds | HexRefEnds) - lex.RefStart
276        CallOuts.error = Error
277        return CallOuts
278
279def demo_refs(u8data):
280        lgth = len(u8data)
281        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
282        (u8, control, lex) = byteclass.classify_bytes(bit)
283        callouts = parse_refs(lex, 0)
284        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
285                              ('entity refs', bitutil.bitstream2string(callouts.GenRefs, lgth)),
286                              ('decimal char refs', bitutil.bitstream2string(callouts.DecRefs, lgth)),
287                              ('hex char refs', bitutil.bitstream2string(callouts.HexRefs, lgth)),
288                              ('ref delmask', bitutil.bitstream2string(callouts.delmask, lgth)),
289                              ('errors', bitutil.bitstream2string(callouts.error, lgth+1))])
290
291
292class tag_callouts:
293        ElemNames = 0
294        AttNames = 0
295        AttVals = 0
296        Tags = 0
297        EmptyTagEnds = 0
298        EndTags = 0
299        error = 0
300       
301        # POTENTIAL ADDITIONAL FIELDS
302        # StartTagEnds = 0
303        # EmptyTagEnds = 0     
304        # EndTagEnds = 0
305
306def parse_tags(lex, CtCDPI_mask, EOF_mask):
307        """Parse start, empty and end tags, calling out element names, attribute
308        names and values, empty tag positions, and tag extents.
309
310        >>> demo_tags("<root><t1>text</t1><t2 a1='foo' a2 = 'fie'>more</t2><tag3 att3='b'/></root>")
311        input data      : <root><t1>text</t1><t2 a1='foo' a2 = 'fie'>more</t2><tag3 att3='b'/></root>
312        element names   : _1111__11___________11_______________________________1111__________________
313        attribute names : _______________________11_______11________________________1111_____________
314        attribute values: __________________________11111______11111_____________________111_________
315        empty tag marks : ___________________________________________________________________1_______
316        end tags        : _______________111______________________________111__________________11111_
317        start/empty tags: _1111__11___________1111111111111111111111___________11111111111111________
318        errors          : ____________________________________________________________________________
319
320        Attributes can use double quotes.
321
322        >>> demo_tags('<dquote_atts a1="1234" attribute2="4321"/>')
323        input data      : <dquote_atts a1="1234" attribute2="4321"/>
324        element names   : _11111111111______________________________
325        attribute names : _____________11________1111111111_________
326        attribute values: ________________111111____________111111__
327        empty tag marks : _________________________________________1
328        end tags        : __________________________________________
329        start/empty tags: _1111111111111111111111111111111111111111_
330        errors          : ___________________________________________
331
332        Syntax errors of various types are identified with the error stream.
333
334        1. Element name missing errors.
335
336        >>> demo_tags("< noname='flawed'/> ")
337        input data      : < noname='flawed'/>
338        element names   : ____________________
339        attribute names : __111111____________
340        attribute values: _________11111111___
341        empty tag marks : __________________1_
342        end tags        : ____________________
343        start/empty tags: _11111111111111111__
344        errors          : _1___________________
345
346        2. Missing attribute names.
347
348        >>> demo_tags("<noatt ='flawed'/>  <one_att a1='good' = 'bad'> oops </one_att>")
349        input data      : <noatt ='flawed'/>  <one_att a1='good' = 'bad'> oops </one_att>
350        element names   : _11111_______________1111111___________________________________
351        attribute names : _____________________________11________________________________
352        attribute values: ________11111111________________111111___11111_________________
353        empty tag marks : _________________1_____________________________________________
354        end tags        : ______________________________________________________11111111_
355        start/empty tags: _1111111111111111____1111111111111111111111111_________________
356        errors          : _______1_______________________________1________________________
357
358        3. Missing or incorrect = sign.
359
360        >>> demo_tags('<errata plusforeq+"5678" noequals"90" />')
361        input data      : <errata plusforeq+"5678" noequals"90" />
362        element names   : _111111_________________________________
363        attribute names : ________111111111________11111111_______
364        attribute values: __________________111111__________111111
365        empty tag marks : ________________________________________
366        end tags        : ________________________________________
367        start/empty tags: _111111111111111111111111111111111111111
368        errors          : _________________1_______________11______
369
370        4.  Missing whitespace
371
372        >>> demo_tags("<jammed att='value'att2='v2' />")
373        input data      : <jammed att='value'att2='v2' />
374        element names   : _111111________________________
375        attribute names : ________111________1111________
376        attribute values: ____________1111111_____1111___
377        empty tag marks : ______________________________1
378        end tags        : _______________________________
379        start/empty tags: _11111111111111111111111111111_
380        errors          : ___________________1____________
381
382        5.  Extra whitespace in an empty tag.
383
384        >>> demo_tags("<extrawhite / >")
385        input data      : <extrawhite / >
386        element names   : _1111111111____
387        attribute names : _______________
388        attribute values: _______________
389        empty tag marks : _____________1_
390        end tags        : _______________
391        start/empty tags: _111111111111__
392        errors          : _____________1__
393
394        6.  Unterminated or incorrectly terminated attribute values
395
396        >>> demo_tags("<badattvalues a='blud<   b='455>   ")
397        input data      : <badattvalues a='blud<   b='455>   
398        element names   : _111111111111______________________
399        attribute names : ______________1__________1_________
400        attribute values: ________________111111_____11111111
401        empty tag marks : ___________________________________
402        end tags        : ___________________________________
403        start/empty tags: _111111111111111111111_111111111111
404        errors          : _____________________11____________1
405
406        7.  Unterminated tags
407
408        >>> demo_tags("<unterminated a='245'  ")
409        input data      : <unterminated a='245' 
410        element names   : _111111111111__________
411        attribute names : ______________1________
412        attribute values: ________________11111__
413        empty tag marks : _______________________
414        end tags        : _______________________
415        start/empty tags: _1111111111111111111111
416        errors          : _______________________1
417
418"""
419        callouts = tag_callouts()
420       
421        # Delimiters for scans.
422        DQuoteScan = ~(lex.DQuote | lex.LAngle) & EOF_mask
423        SQuoteScan = ~(lex.SQuote | lex.LAngle) & EOF_mask
424        AttListDelim = lex.Slash | lex.RAngle
425       
426        # Start the parallel parsing by inspecting the character
427        # after the opening "<" of a tag.
428        LAngleFollow = lex.LAngle_scope &~ CtCDPI_mask
429        ElemNamePositions = LAngleFollow & ~lex.Slash
430        EndTagSeconds = LAngleFollow & lex.Slash
431       
432        # Start Tag/Empty Element Tag Parsing
433
434        # Advance all cursors by scanning through the tag name.
435        ElemNameFollows = bitutil.ScanThru(ElemNamePositions, lex.NameScan)
436        # Must have at least one name character for a legal start tag.
437        # Mark any occurrences of null names as errors.
438        ParseError = ElemNamePositions & ElemNameFollows
439        callouts.ElemNames = ElemNameFollows - ElemNamePositions
440       
441        # Initialize the accumulators for attribute name and value positions.
442        AttNameStarts = 0 
443        AttNameFollows = 0
444        EqToCheck = 0
445        AttValStarts = 0
446        AttValEnds = 0
447        AttValFollows = 0
448
449        # After the element name, there may or may not be an attlist.
450        AfterWS = bitutil.ScanThru(ElemNameFollows, lex.WS)
451        AttListEnd = AfterWS & AttListDelim
452        AttNameStart = AfterWS & ~AttListDelim
453        # At least one WS character is required between ElemNames and AttNames.
454        ParseError |= ElemNameFollows & AttNameStart
455
456        #
457        # The following loop iterates through attributes within a start tag.
458        # Because all start tags are processed in parallel, the number of
459        # iterations is the maximum number of attributes found in any one
460        # start tag, plus one.
461        while AttNameStart:
462                AttNameStarts |= AttNameStart
463                AttNameFollow = bitutil.ScanThru(AttNameStart, lex.NameScan)
464                AttNameFollows |= AttNameFollow
465                # Scan through WS to the expected '=' delimiter.
466                EqExpected = bitutil.ScanThru(AttNameFollow, lex.WS)
467                EqToCheck |= EqExpected
468                AttValPos = bitutil.ScanThru(bitutil.Advance(EqExpected), lex.WS)
469                AttValStarts |= AttValPos
470                DQuoteAttVal = AttValPos & lex.DQuote
471                SQuoteAttVal = AttValPos & lex.SQuote
472                DQuoteAttEnd = bitutil.ScanThru(bitutil.Advance(DQuoteAttVal), DQuoteScan)
473                SQuoteAttEnd = bitutil.ScanThru(bitutil.Advance(SQuoteAttVal), SQuoteScan)
474                AttValEnd = DQuoteAttEnd | SQuoteAttEnd
475                AttValEnds |= AttValEnd
476                AttValFollow = bitutil.Advance(AttValEnd)
477                AttValFollows |= AttValFollow
478                AfterWS = bitutil.ScanThru(AttValFollow, lex.WS)
479                AttListEnd |= AfterWS & AttListDelim
480                AttNameStart = AfterWS & ~AttListDelim
481
482        # No more attribute values to process when AttNameStart == 0.
483
484        callouts.AttNames = AttNameFollows - AttNameStarts
485        callouts.AttVals = AttValFollows - AttValStarts
486        STagEnds = AttListEnd & lex.RAngle
487        # Mark any "/" characters found as the ends of empty element tags.
488        callouts.EmptyTagMarks = bitutil.Advance(AttListEnd & lex.Slash)
489        callouts.Tags = (STagEnds | callouts.EmptyTagMarks) - ElemNamePositions
490
491        # Check for errors.
492        ParseError |= AttValFollows & AttNameStarts # No intervening WS.
493        ParseError |= AttNameStarts & AttNameFollows # Null AttName
494        ParseError |= EqToCheck & ~lex.Equals # = not found where expected.
495        ParseError |= AttValStarts & ~ (lex.DQuote | lex.SQuote)
496        ParseError |= AttValEnds & ~ (lex.DQuote | lex.SQuote)
497        ParseError |= callouts.EmptyTagMarks & ~lex.RAngle
498
499        # End Tag Parsing
500        EndTagEnds = bitutil.ScanThru(bitutil.ScanThru(bitutil.Advance(EndTagSeconds), lex.NameScan), lex.WS)
501        ParseError |= EndTagEnds & ~lex.RAngle
502        callouts.EndTags = EndTagEnds - EndTagSeconds
503        callouts.error = ParseError
504
505        # POTENTIAL ADDITIONAL FIELDS
506        # callouts.StartTagEnds = STagEnds
507        # callouts.EmptyTagEnds = bitutil.Advance(callouts.EmptyTagMarks)
508        # callouts.EndTagEnds = EndTagEnds
509       
510        return callouts
511
512def demo_tags(u8data):
513        lgth = len(u8data)
514        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
515        (u8, control, lex) = byteclass.classify_bytes(bit)
516        lex = add_multiliterals(lex)
517        markup1 = parse_CtCDPI(lex, EOF_mask)
518        callouts = parse_tags(lex, markup1.CtCDPI_mask, EOF_mask)
519        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
520                              ('element names', bitutil.bitstream2string(callouts.ElemNames, lgth)),
521                              ('attribute names', bitutil.bitstream2string(callouts.AttNames, lgth)),
522                              ('attribute values', bitutil.bitstream2string(callouts.AttVals, lgth)),
523                              ('empty tag marks', bitutil.bitstream2string(callouts.EmptyTagMarks, lgth)),
524                              ('end tags', bitutil.bitstream2string(callouts.EndTags, lgth)),
525                              ('start/empty tags', bitutil.bitstream2string(callouts.Tags, lgth)),
526                              ('errors', bitutil.bitstream2string(callouts.error, lgth+1))])
527
528
529
530def validate_no_CD_end(lex, markup1, tags):
531        """Find illegal occurrences of ]]> in text (outside of markup).
532
533        >>> demo_validate_no_CD_end(' <!-- OK: ]]>  --> <![CDATA OK  ]]>  ]]> <tag att=" ]]> "/> ]]>  <?php ]]> ?> ')
534        input data :  <!-- OK: ]]>  --> <![CDATA OK  ]]>  ]]> <tag att=" ]]> "/> ]]>  <?php ]]> ?>
535        CtCDPI_mask: __1111111111111111__111111111111111_______________________________11111111111_
536        tags       : __________________________________________1111111111111111____________________
537        illegal ]]>: _______________________________________1______________________1_______________
538"""
539        return lex.CD_end & ~(markup1.CtCDPI_mask | tags.Tags)
540
541def demo_validate_no_CD_end(u8data):
542        lgth = len(u8data)
543        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
544        (u8, control, lex) = byteclass.classify_bytes(bit)
545        lex = add_multiliterals(lex)
546        markup1 = parse_CtCDPI(lex, EOF_mask)
547        tags = parse_tags(lex, markup1.CtCDPI_mask, EOF_mask)
548        error = validate_no_CD_end(lex, markup1, tags)
549        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
550                              ('CtCDPI_mask', bitutil.bitstream2string(markup1.CtCDPI_mask, lgth)),
551                              ('tags', bitutil.bitstream2string(tags.Tags, lgth)),
552                              ('illegal ]]>', bitutil.bitstream2string(error, lgth))])
553
554
555def prevalidate_names(u8, lex, name_stream, nmtoken_stream):
556        """  Fully validate ASCII-based names and identify non-ASCII positions within names.
557        >>> demo_prevalidate_names("<good -bad='hyphen'/><_OK/><:funny:butOK/><1problem a='b' d423='x'>")
558        input data      : <good -bad='hyphen'/><_OK/><:funny:butOK/><1problem a='b' d423='x'>
559        names           : _1111_1111____________111___111111111111___11111111_1_____1111_____
560        name_start_check: ______1____________________________________1_______________________
561        name_check      : ___________________________________________________________________
562"""
563        name_start = name_stream &~ bitutil.Advance(name_stream)
564        name_start_check = name_start & ~lex.ASCII_name_start
565        name_check = (name_stream &~ name_start | nmtoken_stream) & ~lex.ASCII_name_char & ~u8.suffix
566        return (name_start_check, name_check)
567
568def demo_prevalidate_names(u8data):
569        lgth = len(u8data)
570        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
571        (u8, control, lex) = byteclass.classify_bytes(bit)
572        lex = add_multiliterals(lex)
573        markup1 = parse_CtCDPI(lex, EOF_mask)
574        callouts = parse_tags(lex, markup1.CtCDPI_mask, EOF_mask)
575        name_stream = callouts.ElemNames | callouts.AttNames
576        (name_start_check, name_check) = prevalidate_names(u8, lex, name_stream, 0)
577        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
578                              ('names', bitutil.bitstream2string(name_stream, lgth)),
579                              ('name_start_check', bitutil.bitstream2string(name_start_check, lgth)),
580                              ('name_check', bitutil.bitstream2string(name_check, lgth))])
581
582def validate_namespace_names(lex, name_stream):
583        """ Ensure that any colon (namespace separator) in a name divides the
584        name into nonempty namespace prefix and local-part components, neither
585        of which contain colons.
586        >>> demo_validate_namespace_names("<a:b  xmlns: = '3' :x = '1' y: = '2'/>")
587        input data  : <a:b  xmlns: = '3' :x = '1' y: = '2'/>
588        names       : _111__111111_______11_______11________
589        NCname_error: ____________1______1__________1_______
590        >>> demo_validate_namespace_names("<a  xmlns:g = '3' a:x = '1' y::b = '2'/>")
591        input data  : <a  xmlns:g = '3' a:x = '1' y::b = '2'/>
592        names       : _1__1111111_______111_______1111________
593        NCname_error: ______________________________1_________
594        """
595        name_cursor = name_stream & ~bitutil.Advance(name_stream)
596        void_prefix_err = name_cursor & lex.Colon
597        namespace_sep = bitutil.ScanThru(name_cursor, lex.NameScan &~ lex.Colon) & lex.Colon
598        local_part_start = bitutil.Advance(namespace_sep)
599        local_part_err = local_part_start &~ lex.NameScan
600        colon2_err = bitutil.ScanThru(local_part_start, lex.NameScan &~ lex.Colon) & lex.Colon
601        return void_prefix_err | local_part_err | colon2_err
602       
603def demo_validate_namespace_names(u8data):
604        lgth = len(u8data)
605        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
606        (u8, control, lex) = byteclass.classify_bytes(bit)
607        lex = add_multiliterals(lex)
608        markup1 = parse_CtCDPI(lex, EOF_mask)
609        callouts = parse_tags(lex, markup1.CtCDPI_mask, EOF_mask)
610        name_stream = callouts.ElemNames | callouts.AttNames
611        name_check = validate_namespace_names(lex, name_stream)
612        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
613                              ('names', bitutil.bitstream2string(name_stream, lgth)),
614                              ('NCname_error', bitutil.bitstream2string(name_check, lgth))])
615
616
617def parabix_parse(u8data):
618        # Transpose to parallel bit streams and prepare an EOF mask.
619        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
620
621        # Classify bytes for UTF-8 processing, whitespace and control
622        # processing and XML lexical analysis.
623        #(u8, control, lex) = byteclass.classify_bytes(bit)
624        (u8, control, lex) = byteclass.classify_bytes_with_shift1opt(bit)
625
626        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
627        u8 = u8u16.validate_utf8(u8)
628
629        # Rule out the illegal characters for XML.
630        xmlchar_error = validate_xmlchar(u8, control, lex, EOF_mask)
631
632        # Find and normalize bare CR or CRLF combinations.
633        (control, bit) = normalize_line_breaks(control, bit)
634
635        # Compute XML multilterals such as <?, </, --, ]]>.
636        lex = add_multiliterals(lex)
637
638        # Parse all comments, CDATA sections and processing instructions.
639        markup1 = parse_CtCDPI(lex, EOF_mask)
640
641        # All remaining "<" must be tag start characters; parse tags.
642        tags = parse_tags(lex, markup1.CtCDPI_mask, EOF_mask)
643
644        # All remaining "&" must be reference start characters; parse them.
645        refs = parse_refs(lex, markup1.CtCDPI_mask)
646
647        # Ensure that no occurrence of ]]> occurs outside of markup.
648        CD_end_error = validate_no_CD_end(lex, markup1, tags)
649
650        # Convert to UTF-16 bit streams.
651        (u16hi, u16lo, u16delmask) = u8u16.u8u16(u8, bit)
652
653        # Consolidate and check for errors
654        error = u8.error | xmlchar_error | markup1.error | tags.error | CD_end_error | refs.error
655
656        # Consolidate the deletion_masks
657        delmask = control.CRLF | refs.delmask | u16delmask # | markup1.CDATA_delimiters
658
659        return (markup1, tags, refs, u16hi, u16lo, delmask, error, lex, u16delmask, EOF_mask)
660
661
662def demo_parabix(u8data):
663
664        lgth = len(u8data)
665       
666        (markup1, tags, refs, u16hi, u16lo, delmask, error, lex, u16delmask, EOF_mask) = parabix_parse(u8data)
667        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
668                              ('input high nybbles', bitutil.high_nybble_stream(u8data)), 
669                              ('input low nybbles', bitutil.low_nybble_stream(u8data)),
670                              ('CD_span', bitutil.bitstream2string(markup1.CD_span, lgth)),
671                              ('Ct_span', bitutil.bitstream2string(markup1.Ct_span, lgth)),
672                              ('PI_span', bitutil.bitstream2string(markup1.PI_span, lgth)),
673                              ('CtCDPI_mask', bitutil.bitstream2string(markup1.CtCDPI_mask, lgth)),
674                              ('entity refs', bitutil.bitstream2string(refs.GenRefs, lgth)),
675                              ('decimal char refs', bitutil.bitstream2string(refs.DecRefs, lgth)),
676                              ('hex char refs', bitutil.bitstream2string(refs.HexRefs, lgth)),
677                              ('element names', bitutil.bitstream2string(tags.ElemNames, lgth)),
678                              ('attribute names', bitutil.bitstream2string(tags.AttNames, lgth)),
679                              ('attribute values', bitutil.bitstream2string(tags.AttVals, lgth)),
680                              ('empty tag marks', bitutil.bitstream2string(tags.EmptyTagMarks, lgth)),
681                              ('end tags', bitutil.bitstream2string(tags.EndTags, lgth)),
682                              ('start/empty tags', bitutil.bitstream2string(tags.Tags, lgth)),
683                              ('delmask', bitutil.bitstream2string(delmask, lgth)),
684                              ('u16delmask', bitutil.bitstream2string(u16delmask, lgth)),
685                              ('errors', bitutil.bitstream2string(error, lgth+1))])
686
687def demo_u16delmask(u8data):
688
689        u8len = len(u8data)
690       
691        # Transpose to parallel bit streams and prepare an EOF mask.
692        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
693
694        # Classify bytes for UTF-8 processing, whitespace and control
695        # processing and XML lexical analysis.
696        (u8, control, lex) = byteclass.classify_bytes(bit)
697
698        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
699        u8 = u8u16.validate_utf8(u8)   
700       
701        # Convert to UTF-16 bit streams.
702        (u16hi, u16lo, delmask) = u8u16.u8u16(u8, bit)
703       
704        # Inverse transpose
705        U16H = bitutil.filter_bytes(bitutil.inverse_transpose(u16hi, u8len), delmask)
706        U16L = bitutil.filter_bytes(bitutil.inverse_transpose(u16lo, u8len), delmask)
707       
708        # Construct UTF-16 data buffer
709        bytes = bitutil.merge_bytes(U16L, U16H)
710       
711        U16data = bytes.decode('utf16')
712       
713        bitutil.print_aligned_u8_byte_streams([('input data', u8data), 
714                                ('u16delmask', bitutil.bitstream2string(delmask, u8len)),               
715                                    ('errors', bitutil.bitstream2string(u8.error, u8len+1))])
716        return
717
718if __name__ == "__main__":
719        import doctest
720        doctest.testmod()
721       
722        if len(sys.argv) > 1:
723                u8data = bitutil.readfile(sys.argv[1]) 
724#               demo_validate_xmlchar(u8data)
725#               demo_line_breaks(u8data)
726#               demo_multiliterals(u8data)
727#               demo_CtCDPI(u8data)
728#               demo_refs(u8data)
729#               demo_tags(u8data)
730#               demo_validate_no_CD_end(u8data)         
731#               demo_u16delmask(u8data)         
732                demo_parabix(u8data)
733#               demo_u16delmask(u8data)
734        else:
735                print("Usage: python parabix2.py <file>")       
736               
737 
738       
739       
Note: See TracBrowser for help on using the repository browser.