source: proto/JSON/json_prototype.py @ 687

Last change on this file since 687 was 687, checked in by ksherdy, 9 years ago

Update Errors streams to include lgth+1. Add 0e error case.

File size: 15.4 KB
Line 
1# -*- coding: utf-8 -*-
2#
3# json_prototype.py
4#
5# Ken Herdy
6# Oct. 13, 2010
7#
8#----------------------------------------------------------------------------
9#
10# We use python's unlimited precision integers for unbounded bit streams.
11# This permits simple logical operations on the entire stream.
12# Assumption: bitstreams are little-endian (e.g., as on x86).
13#
14#----------------------------------------------------------------------------
15#
16
17import bitutil
18import byteclass
19import u8u16
20import math
21import sys
22
23debug = False
24filename = "json_prototype.py"
25
26# Globals
27#
28# Bitstream function defs input/output *only* bitstream type variables.
29# Global declarations allow debug blocks in bitstream defs. Do not shadow variables.
30u8data = ""
31lgth = 0
32
33def simd_const_4(hexdigit,EOF_mask):
34        r"""
35        IDISA library function.
36        """
37        lgth = bitutil.count_leading_zeroes(~EOF_mask)/4
38        return int(hexdigit*(lgth+1),16)&EOF_mask
39       
40def parse_escape(Lex, EOF_mask):
41        r"""
42        Marks escaped characters.
43        Does not mark escaped '\' characters.
44        '\' characters are either escaped and unmarked or the following character in an odd length run is marked.
45        """
46
47        odd = simd_const_4('a',EOF_mask)
48        even = simd_const_4('5',EOF_mask)
49       
50        start = Lex.RSolidus &~ bitutil.Advance(Lex.RSolidus)
51       
52        even_start = start & even
53        even_final = (even_start + Lex.RSolidus) & ~Lex.RSolidus
54        even_escape = even_final & odd
55       
56        odd_start = start & odd
57        odd_final = (odd_start + Lex.RSolidus) & ~Lex.RSolidus
58        odd_escape = (odd_final & even)
59
60        escape = (even_escape | odd_escape) 
61       
62        return escape
63       
64def demo_parse_escape(u8data):
65        global lgth
66        lgth = len(u8data)
67
68        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
69        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
70        (escape) = parse_escape(Lex,EOF_mask)
71
72        bitutil.print_aligned_streams([('Input Data', u8data), 
73                              ('Lex.RSolidus', bitutil.bitstream2string(Lex.RSolidus, lgth)),   
74                              ('escape', bitutil.bitstream2string(escape, lgth)),       
75                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
76        return
77
78def parallel_prefix_parity(strm,lgth):
79        r"""
80        Translate to library function.
81       
82        x y  x XOR y
83        ------------
84        0 0   0
85        0 1   1
86        1 0   1
87        0 0   0
88
89        Let n = length(bitstream).
90
91        Define Pk,i as the parity of the bit range [k-(k+2^i),k] for bit positions n >= k >= 1.
92       
93        Base Case: Pk,0 = bitstream at position k, for all k, n >= k >= 0.
94        Inductive Step: Pk,i+1 = (Pk,i << 2^i) XOR Pk,i.
95       
96        Pk,ceil(log(n) denotes the parity of the bit position k, n >= k >= 0.
97       
98        bitstream[k] = 1 --> odd parity
99        bitstream[k] = 0 --> even parity
100        """
101        t1 = strm
102        for i in range(0,int(math.ceil(math.log(lgth,2)))):
103                t2 = t1 ^ (t1 << pow(2,i))
104                t1 = t2
105        return t2 
106
107def demo_parallel_prefix_parity(u8data):
108        r"""
109        >>> demo_parallel_prefix_parity('"data" "data""data" "data" "data')
110        Input Data: "data" "data""data" "data" "data
111        Lex.DQuote: 1____1_1____11____1_1____1_1____
112        Parity    : 11111__11111_11111__11111__11111
113        EOF_Mask  : 11111111111111111111111111111111_
114        <BLANKLINE>
115        """
116        global lgth
117        lgth = len(u8data)
118
119        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
120        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
121        Parity = parallel_prefix_parity(Lex.DQuote,lgth)
122
123        bitutil.print_aligned_streams([('Input Data', u8data), 
124                              ('Lex.DQuote', bitutil.bitstream2string(Lex.DQuote, lgth)),
125                              ('Parity', bitutil.bitstream2string(Parity, lgth)),       
126                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
127        return
128
129
130def validate_number(Lex, EOF_mask):
131        r"""   
132        RFC 4627 - JavaScript Object Notation (JSON) 
133        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
134
135        number = [ minus ] int [ frac ] [ exp ]
136        decimal-point = %x2E       ; .
137        digit1-9 = %x31-39         ; 1-9
138        e = %x65 / %x45            ; e E
139        exp = e [ minus / plus ] 1*DIGIT
140        frac = decimal-point 1*DIGIT
141        int = zero / ( digit1-9 *DIGIT )
142        minus = %x2D               ; -
143        plus = %x2B                ; +
144        zero = %x30                ; 0 
145        """     
146        Errors = 0
147        M0 = 0                                                  # Assume the cursor is at the first Minus, Zero, or Digit_1_9 character
148        M0 = bitutil.Advance(Lex.Comma)                         # WARNING - A hack to set initial cursor postions and ease testing. The 'lexical' FIRST SET for the JSON number production is {-,0,1,..,9} .     
149
150        M1 = bitutil.ScanThru(M0, Lex.Minus & M0)               # ? Optional character class [-]
151        E1 = M1 &~(Lex.Zero|Lex.Digit1_9)
152
153        M1a = M1 & Lex.Zero                                     # Split
154        M1b = M1 & Lex.Digit0_9                         
155        M2a = bitutil.Advance(M1a)
156        M2b = bitutil.Advance(M1b)
157        M3b = bitutil.ScanThru(M2b,Lex.Digit0_9)
158        M4 = M2a | M3b                                          # Join
159       
160        M4a = M4 &~(Lex.DecimalPoint)                           # Split
161        M4b = M4 & (Lex.DecimalPoint)
162        M5b = bitutil.Advance(M4b)
163        E5b = M5b &~(Lex.Digit0_9)                              # + [0-9]+
164        M6 = bitutil.ScanThru(M5b,Lex.Digit0_9)
165        M7 = M4a | M6                                           # Join
166       
167        M7a = M7 &~(Lex.Ee)                                     # Split
168        E7a = M7a &~(Lex.NumberFollowSet)
169        M7b = M7 &(Lex.Ee)
170        M8b = bitutil.Advance(M7b)
171        M9b = bitutil.ScanThru(M8b, Lex.PlusMinus & M8b)        # ? Optional character class [+-]               
172        E9b  = M9b &~(Lex.Digit0_9)                             # + [0-9]+
173        M10b = bitutil.ScanThru(M9b,Lex.Digit0_9)
174        E10b = M10b &~(Lex.NumberFollowSet)
175        M11 = M7a | M10b                                        # Join
176       
177        Errors = E1 | E5b | E7a | E9b | E10b
178       
179        if debug:
180                bitutil.print_aligned_streams([('Input Data', u8data), 
181                              ('M0', bitutil.bitstream2string(M0, lgth)),
182                              ('M1', bitutil.bitstream2string(M1, lgth)),
183                              ('E1', bitutil.bitstream2string(E1, lgth)),
184                              ('M1a', bitutil.bitstream2string(M1a, lgth)),
185                              ('M2a', bitutil.bitstream2string(M2a, lgth)),
186                              ('M2b', bitutil.bitstream2string(M2b, lgth)),
187                              ('M3b', bitutil.bitstream2string(M3b, lgth)),
188                              ('M4', bitutil.bitstream2string(M4, lgth)),
189                              ('M4a', bitutil.bitstream2string(M4a, lgth)),
190                              ('M4b', bitutil.bitstream2string(M4b, lgth)),
191                              ('M5b', bitutil.bitstream2string(M5b, lgth)),
192                              ('E5b', bitutil.bitstream2string(E5b, lgth)),           
193                              ('M6', bitutil.bitstream2string(M6, lgth)),
194                              ('M7', bitutil.bitstream2string(M7, lgth)),
195                              ('M7a', bitutil.bitstream2string(M7a, lgth)),
196                              ('E7a', bitutil.bitstream2string(E7a, lgth)),                                                   
197                              ('M7b', bitutil.bitstream2string(M7b, lgth)),
198                              ('M8b', bitutil.bitstream2string(M8b, lgth)),
199                              ('M9b', bitutil.bitstream2string(M9b, lgth)),           
200                              ('E9b', bitutil.bitstream2string(E9b, lgth)),           
201                              ('M10b', bitutil.bitstream2string(M10b, lgth)),                         
202                              ('M11', bitutil.bitstream2string(M11, lgth)),                                                   
203                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])           
204        return Errors
205
206def demo_validate_number(u8data):
207        r"""
208        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
209        Input Data  : ,-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,
210        Minus       : _1_11_1_____1___1___1____1_______1_______1_________________________
211        Zero        : _________11__11__1___1____1___11___________1______1__1__1__________
212        Digit1_9    : __________________________________111_111____111____1____111111111_
213        Digit0_9    : _________11__11__1___1____1___11__111_111__1_111__1_11__1111111111_
214        DecimalPoint: __________________1___1____1_________1______1______________________
215        Ee          : _______________________1____1______________________1_______________
216        PlusMinus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
217        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111_
218        Errors      : __1_1__1__1___1____1___1____1__1_________1______1_____1__1_________
219        <BLANKLINE>
220        """
221        r"""
222        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
223        Input Data  : ,0.5,98.6,99.44,1066,1e1,0.1e1,1e-1,1e00,2e+00,2e-00,1234567890,-9876.543210,0.123456789e-12,1.234567890E+34,23456789012E66,
224        Minus       : _________________________________1_______________1______________1________________________1__________________________________
225        Zero        : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
226        Digit1_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
227        Digit0_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
228        DecimalPoint: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
229        Ee          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
230        PlusMinus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
231        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
232        Errors      : ____________________________________________________________________________________________________________________________
233        <BLANKLINE>
234        """
235        r"""
236        >>> demo_validate_number(',012345,12345,0,00,-0,-00')
237        Input Data  : ,012345,12345,0,00,-0,-00
238        Minus       : ___________________1__1__
239        Zero        : _1____________1_11__1__11
240        Digit1_9    : __11111_11111____________
241        Digit0_9    : __11111_11111____________
242        DecimalPoint: _________________________
243        Ee          : _________________________
244        PlusMinus   : ___________________1__1__
245        EOF_Mask    : 1111111111111111111111111_
246        Errors      : __1______________1______1
247        <BLANKLINE>
248        """ 
249        global lgth
250        lgth = len(u8data)
251
252        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
253        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
254        Errors = validate_number(Lex,EOF_mask)
255
256        bitutil.print_aligned_streams([('Input Data', u8data), 
257                              ('Minus', bitutil.bitstream2string(Lex.Minus, lgth)),
258                              ('Zero', bitutil.bitstream2string(Lex.Zero, lgth)),
259                              ('Digit1_9', bitutil.bitstream2string(Lex.Digit1_9, lgth)),
260                              ('Digit0_9', bitutil.bitstream2string(Lex.Digit0_9, lgth)),
261                              ('DecimalPoint', bitutil.bitstream2string(Lex.DecimalPoint, lgth)),
262                              ('Ee', bitutil.bitstream2string(Lex.Ee, lgth)),
263                              ('PlusMinus', bitutil.bitstream2string(Lex.PlusMinus, lgth)),
264                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
265                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])
266
267def validate_string(Lex,Ctrl,StringMask,EscapeChars,EOF_mask,lgth):
268        r"""
269        RFC 4627 - JavaScript Object Notation (JSON) 
270
271        string = quotation-mark *char quotation-mark
272        char = unescaped /
273              escape (
274                  %x22 /          ; "    quotation mark  U+0022
275                  %x5C /          ; \    reverse solidus U+005C
276                  %x2F /          ; /    solidus         U+002F
277                  %x62 /          ; b    backspace       U+0008
278                  %x66 /          ; f    form feed       U+000C
279                  %x6E /          ; n    line feed       U+000A
280                  %x72 /          ; r    carriage return U+000D
281                  %x74 /          ; t    tab             U+0009
282                  %x75 4HEXDIG )  ; uXXXX                U+XXXX
283
284        escape = %x5C              ; \
285        quotation-mark = %x22      ; "
286        unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
287
288        JSON string validation requires both:
289        (1) validation of escape characters,
290        (2) validation of unescaped characters.
291        """
292       
293        # (1) Validate escape characters
294        StringEscapeChars = EscapeChars & StringMask
295        Errors = (StringEscapeChars &~ Lex.Escape)
296       
297        u = StringEscapeChars & Lex.u
298       
299        uScope1 = bitutil.Advance(u)
300        uScope2 = bitutil.Advance(uScope1)
301        uScope3 = bitutil.Advance(uScope2)
302        uScope4 = bitutil.Advance(uScope3)
303       
304        Errors |= uScope1 &~ Lex.HexDigit
305        Errors |= uScope2 &~ Lex.HexDigit
306        Errors |= uScope3 &~ Lex.HexDigit
307        Errors |= uScope4 &~ Lex.HexDigit
308       
309        # (2) Validation of unescaped characters
310        # (2.1) StringMask construction ensures all '"' are escaped.
311        # (2.2) '\' are either correctly escaped or the character following an odd length run is escaped.
312        # (2.3) validate_utf8(u8) ensures valid UTF8 encodings in the code point range U+0000 - U+01FFFF. TODO
313
314        StringNotEscapedChars = (~(EscapeChars | Lex.RSolidus)) & StringMask # TODO - Verify logic.
315        Errors |= (StringNotEscapedChars & Ctrl.x00_x1F)
316               
317        if debug:
318                bitutil.print_aligned_streams([('Input Data', u8data), 
319                              ('EscapeChars', bitutil.bitstream2string(EscapeChars, lgth)),
320                              ('StringEscapeChars', bitutil.bitstream2string(StringEscapeChars, lgth)),
321                              ('u', bitutil.bitstream2string(u, lgth)),
322                              ('uScope1', bitutil.bitstream2string(uScope1, lgth)),
323                              ('uScope2', bitutil.bitstream2string(uScope2, lgth)),
324                              ('uScope3', bitutil.bitstream2string(uScope3, lgth)),
325                              ('uScope4', bitutil.bitstream2string(uScope4, lgth)),
326                              ('StringNotEscapedChars', bitutil.bitstream2string(StringNotEscapedChars, lgth)),
327                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])     
328        return Errors
329
330def demo_validate_string(u8data):
331        r"""
332        >>> demo_validate_string('"\u abcd" "\u1___" "\u12__" "\u123_"')
333        Input Data      : "\u abcd" "\u1___" "\u12__" "\u123_"
334        EscapeChars     : __1_________1________1________1_____
335        UnescapedDQuotes: 1_______1_1______1_1______1_1______1
336        ParityMask      : 11111111__1111111__1111111__1111111_
337        StringMask      : _1111111___111111___111111___111111_
338        StringCursorEnd : ________1________1________1________1_
339        EOF_Mask        : 111111111111111111111111111111111111_
340        Errors          : ___1__________111_______11________1__
341        <BLANKLINE>
342        """ 
343        global lgth
344        lgth = len(u8data)
345
346        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
347        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
348       
349        # Construct string interior mask (1),(2),(3)
350        # (1) Mark all escaped characters
351        EscapeChars = parse_escape(Lex, EOF_mask)
352       
353        # (2) Mark all unescaped "
354        UnescapedDQuotes = (Lex.DQuote &~ EscapeChars)
355       
356        # (3) Construct mask
357        ParityMask = parallel_prefix_parity(UnescapedDQuotes, lgth) & EOF_mask # TODO - Solve EOF_mask problem
358        StringMask = ParityMask & bitutil.Advance(ParityMask)
359                               
360        Errors = validate_string(Lex,Ctrl,StringMask,EscapeChars,EOF_mask,lgth)
361       
362        # Validate all strings are terminated with an unescaped "
363        StringCursor = ParityMask &~ bitutil.Advance(ParityMask)
364        StringCursorEnd = bitutil.ScanThru(StringCursor, ParityMask)
365        Errors |= StringCursorEnd &~ EOF_mask
366
367        bitutil.print_aligned_streams([('Input Data', u8data), 
368                              ('EscapeChars', bitutil.bitstream2string(EscapeChars, lgth)),
369                              ('UnescapedDQuotes', bitutil.bitstream2string(UnescapedDQuotes, lgth)),
370                              ('ParityMask', bitutil.bitstream2string(ParityMask, lgth)),
371                              ('StringMask', bitutil.bitstream2string(StringMask, lgth)),
372                              ('StringCursorEnd', bitutil.bitstream2string(StringCursorEnd, lgth+1)),
373                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
374                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])   
375                             
376        return
377
378def parse_json(u8data):
379 
380        # Transpose to parallel bit streams and prepare an EOF mask.
381        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
382       
383        # Classify bytes for UTF-8 processing, whitespace, control and JSON lexical analysis.
384        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
385       
386        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
387        u8 = u8u16.validate_utf8(u8) 
388       
389        # Mark escape characters
390        escape = parse_escape(Lex, EOF_mask)
391       
392        return
393 
394def demo_parse_json(u8data):
395 
396        global lgth
397        lgth = len(u8data)
398       
399        parse_json(u8data)
400 
401        return
402
403if __name__ == "__main__":
404        import doctest
405        doctest.testmod()
406
407        if len(sys.argv) < 1:
408                sys.stderr.write("Usage: " + filename + "\n")
409                sys.exit(2)
410
411        u8data = bitutil.readfile(sys.argv[1]) 
412#       demo_parse_escape(u8data)
413#       demo_parallel_prefix_parity(u8data)
414        demo_validate_number(u8data)
415#       demo_validate_string(u8data)
416#       demo_parse_json(u8data)
Note: See TracBrowser for help on using the repository browser.