source: proto/JSON/json_prototype.py @ 684

Last change on this file since 684 was 684, checked in by ksherdy, 8 years ago

General reorganization. Addition of JSON String processing logic.

File size: 13.1 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        odd = simd_const_4('a',EOF_mask)
42        even = simd_const_4('5',EOF_mask)
43       
44        start = lex.RSolidus &~ bitutil.Advance(lex.RSolidus)
45       
46        even_start = start & even
47        even_final = (even_start + lex.RSolidus) & ~lex.RSolidus
48        even_escape = even_final & odd
49       
50        odd_start = start & odd
51        odd_final = (odd_start + lex.RSolidus) & ~lex.RSolidus
52        odd_escape = (odd_final & even)
53       
54        escape = (even_escape | odd_escape)
55       
56        return escape
57       
58def demo_parse_escape(u8data):
59        global lgth
60        lgth = len(u8data)
61
62        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
63        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
64        (escape) = parse_escape(lex,EOF_mask)
65
66        bitutil.print_aligned_streams([('Input Data', u8data), 
67                              ('lex.RSolidus', bitutil.bitstream2string(lex.RSolidus, lgth)),   
68                              ('escape', bitutil.bitstream2string(escape, lgth)),       
69                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
70        return
71
72def parallel_prefix_parity(strm,lgth):
73        r"""
74        Translate to library function.
75       
76        x y  x XOR y
77        ------------
78        0 0   0
79        0 1   1
80        1 0   1
81        0 0   0
82
83        Let n = length(bitstream).
84
85        Define Pk,i as the parity of the bit range [k-(k+2^i),k] for bit positions n >= k >= 1.
86       
87        Base Case: Pk,0 = bitstream at position k, for all k, n >= k >= 0.
88        Inductive Step: Pk,i+1 = (Pk,i << 2^i) XOR Pk,i.
89       
90        Pk,ceil(log(n) denotes the parity of the bit position k, n >= k >= 0.
91       
92        bitstream[k] = 1 --> odd parity
93        bitstream[k] = 0 --> even parity
94        """
95        t1 = strm
96        for i in range(0,int(math.ceil(math.log(lgth,2)))):
97                t2 = t1 ^ (t1 << pow(2,i))
98                t1 = t2
99        return t2 
100
101def demo_parallel_prefix_parity(u8data):
102        r"""
103        >>> demo_parallel_prefix_parity('[data] [data][data] [data] [data')
104        Input Data        : [data] [data][data] [data] [data
105        lex.LSquareBracket: 1______1_____1______1______1____
106        lex.RSquareBracket: _____1______1_____1______1______
107        parity            : 11111__11111_11111__11111__11111
108        EOF_Mask          : 11111111111111111111111111111111_
109        <BLANKLINE>
110        """
111        global lgth
112        lgth = len(u8data)
113
114        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
115        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
116        brackets = (lex.LSquareBracket | lex.RSquareBracket)
117        (parity) = parallel_prefix_parity(brackets,lgth)
118
119        bitutil.print_aligned_streams([('Input Data', u8data), 
120                              ('lex.LSquareBracket', bitutil.bitstream2string(lex.LSquareBracket, lgth)),
121                              ('lex.RSquareBracket', bitutil.bitstream2string(lex.RSquareBracket, lgth)),                             
122                              ('parity', bitutil.bitstream2string(parity, lgth)),       
123                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
124        return
125
126
127def validate_number(lex, EOF_mask):
128        Errors = 0     
129        M0 = 0                                                  # Assume the cursor is at the first Minus, Zero, or Digit_1_9 character
130        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} .     
131
132        M1 = bitutil.ScanThru(M0, lex.Minus & M0)               # ? Optional character class [-]
133        E1 = M1 &~(lex.Zero|lex.Digit1_9)
134
135        M1a = M1 & lex.Zero                                     # Split
136        M1b = M1 & lex.Digit0_9                         
137        M2a = bitutil.Advance(M1a)
138        M2b = bitutil.Advance(M1b)
139        M3b = bitutil.ScanThru(M2b,lex.Digit0_9)
140        M4 = M2a | M3b                                          # Join
141       
142        M4a = M4 &~(lex.DecimalPoint)                           # Split
143        M4b = M4 & (lex.DecimalPoint)
144        M5b = bitutil.Advance(M4b)
145        E5b = M5b &~(lex.Digit0_9)                              # + [0-9]+
146        M6 = bitutil.ScanThru(M5b,lex.Digit0_9)
147        M7 = M4a | M6                                           # Join
148       
149        M7a = M7 &~(lex.Ee)                                     # Split
150        E7a = M7a &~(lex.NumberFollowSet)
151        M7b = M7 &(lex.Ee)
152        M8b = bitutil.Advance(M7b)
153        M9b = bitutil.ScanThru(M8b, lex.PlusMinus & M8b)        # ? Optional character class [+-]               
154        E9b  = M9b &~(lex.Digit0_9)                             # + [0-9]+
155        M10b = bitutil.ScanThru(M9b,lex.Digit0_9)
156        E10b = M10b &~(lex.NumberFollowSet)
157        M11 = M7a | M10b                                        # Join
158       
159        Errors = E1 | E5b | E7a | E10b
160       
161        if debug:
162                bitutil.print_aligned_streams([('Input Data', u8data), 
163                              ('M0', bitutil.bitstream2string(M0, lgth)),
164                              ('M1', bitutil.bitstream2string(M1, lgth)),
165                              ('E1', bitutil.bitstream2string(E1, lgth)),
166                              ('M1a', bitutil.bitstream2string(M1a, lgth)),
167                              ('M2a', bitutil.bitstream2string(M2a, lgth)),
168                              ('M2b', bitutil.bitstream2string(M2b, lgth)),
169                              ('M3b', bitutil.bitstream2string(M3b, lgth)),
170                              ('M4', bitutil.bitstream2string(M4, lgth)),
171                              ('M4a', bitutil.bitstream2string(M4a, lgth)),
172                              ('M4b', bitutil.bitstream2string(M4b, lgth)),
173                              ('M5b', bitutil.bitstream2string(M5b, lgth)),
174                              ('E5b', bitutil.bitstream2string(E5b, lgth)),           
175                              ('M6', bitutil.bitstream2string(M6, lgth)),
176                              ('M7', bitutil.bitstream2string(M7, lgth)),
177                              ('M7a', bitutil.bitstream2string(M7a, lgth)),
178                              ('E7a', bitutil.bitstream2string(E7a, lgth)),                                                   
179                              ('M7b', bitutil.bitstream2string(M7b, lgth)),
180                              ('M8b', bitutil.bitstream2string(M8b, lgth)),
181                              ('M9b', bitutil.bitstream2string(M9b, lgth)),           
182                              ('E9b', bitutil.bitstream2string(E9b, lgth)),           
183                              ('M10b', bitutil.bitstream2string(M10b, lgth)),                         
184                              ('M11', bitutil.bitstream2string(M11, lgth)),                                                   
185                              ('Errors', bitutil.bitstream2string(Errors, lgth))])             
186        return Errors
187
188def demo_validate_number(u8data):
189        r"""   
190        RFC 4627 - JavaScript Object Notation (JSON) 
191        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
192
193        number = [ minus ] int [ frac ] [ exp ]
194        decimal-point = %x2E       ; .
195        digit1-9 = %x31-39         ; 1-9
196        e = %x65 / %x45            ; e E
197        exp = e [ minus / plus ] 1*DIGIT
198        frac = decimal-point 1*DIGIT
199        int = zero / ( digit1-9 *DIGIT )
200        minus = %x2D               ; -
201        plus = %x2B                ; +
202        zero = %x30                ; 0 
203        """
204        r"""
205        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
206        Input Data  : ,-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,
207        Minus       : _1_11_1_____1___1___1____1_______1_______1_________________________
208        Zero        : _________11__11__1___1____1___11___________1______1__1__1__________
209        Digit1_9    : __________________________________111_111____111____1____111111111_
210        Digit0_9    : _________11__11__1___1____1___11__111_111__1_111__1_11__1111111111_
211        DecimalPoint: __________________1___1____1_________1______1______________________
212        Ee          : _______________________1____1______________________1_______________
213        PlusMinus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
214        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111_
215        Errors      : __1_1__1__1___1____1___1____1__1_________1______1_____1__1_________
216        <BLANKLINE>
217        """
218        r"""
219        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
220        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,
221        Minus       : _________________________________1_______________1______________1________________________1__________________________________
222        Zero        : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
223        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_
224        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_
225        DecimalPoint: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
226        Ee          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
227        PlusMinus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
228        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
229        Errors      : ____________________________________________________________________________________________________________________________
230        <BLANKLINE>
231        """
232        r"""
233        >>> demo_validate_number(',012345,12345,0,00,-0,-00')
234        Input Data  : ,012345,12345,0,00,-0,-00
235        Minus       : ___________________1__1__
236        Zero        : _1____________1_11__1__11
237        Digit1_9    : __11111_11111____________
238        Digit0_9    : __11111_11111____________
239        DecimalPoint: _________________________
240        Ee          : _________________________
241        PlusMinus   : ___________________1__1__
242        EOF_Mask    : 1111111111111111111111111_
243        Errors      : __1______________1______1
244        <BLANKLINE>
245        """ 
246        global lgth
247        lgth = len(u8data)
248
249        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
250        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
251        Errors = validate_number(lex,EOF_mask)
252
253        bitutil.print_aligned_streams([('Input Data', u8data), 
254                              ('Minus', bitutil.bitstream2string(lex.Minus, lgth)),
255                              ('Zero', bitutil.bitstream2string(lex.Zero, lgth)),
256                              ('Digit1_9', bitutil.bitstream2string(lex.Digit1_9, lgth)),
257                              ('Digit0_9', bitutil.bitstream2string(lex.Digit0_9, lgth)),
258                              ('DecimalPoint', bitutil.bitstream2string(lex.DecimalPoint, lgth)),
259                              ('Ee', bitutil.bitstream2string(lex.Ee, lgth)),
260                              ('PlusMinus', bitutil.bitstream2string(lex.PlusMinus, lgth)),
261                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
262                              ('Errors', bitutil.bitstream2string(Errors, lgth))])
263
264def validate_string(lex,escape,lgth):
265        r"""
266        RFC 4627 - JavaScript Object Notation (JSON) 
267
268        string = quotation-mark *char quotation-mark
269        char = unescaped /
270              escape (
271                  %x22 /          ; "    quotation mark  U+0022
272                  %x5C /          ; \    reverse solidus U+005C
273                  %x2F /          ; /    solidus         U+002F
274                  %x62 /          ; b    backspace       U+0008
275                  %x66 /          ; f    form feed       U+000C
276                  %x6E /          ; n    line feed       U+000A
277                  %x72 /          ; r    carriage return U+000D
278                  %x74 /          ; t    tab             U+0009
279                  %x75 4HEXDIG )  ; uXXXX                U+XXXX
280
281        escape = %x5C              ; \
282
283        quotation-mark = %x22      ; "
284
285        unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
286        """
287
288        return
289
290def demo_validate_string(u8data):
291
292        global lgth
293        lgth = len(u8data)
294
295        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
296        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
297        escape = parse_escape(lex, EOF_mask)
298       
299        # Mark String starts "
300        unescaped_quotation_marks = (lex.DQuote &~ escape)
301       
302        # Mask String interiors
303        parity_mask = parallel_prefix_parity(unescaped_quotation_marks, lgth)
304        string_mask = parity_mask & bitutil.Advance(parity_mask)
305       
306       
307       
308        errors = validate_string(lex,escape,lgth)
309       
310        errors = 1 
311       
312        bitutil.print_aligned_streams([('Input Data', u8data), 
313                              ('escape', bitutil.bitstream2string(escape, lgth)),
314                              ('DQuote', bitutil.bitstream2string(lex.DQuote, lgth)),
315                              ('unescaped_quotation_marks', bitutil.bitstream2string(unescaped_quotation_marks, lgth)),
316                              ('string_mask', bitutil.bitstream2string(string_mask, lgth)),                           
317                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
318                              ('errors', bitutil.bitstream2string(errors, lgth))])     
319                             
320        return
321
322def parse_json(u8data):
323 
324        # Transpose to parallel bit streams and prepare an EOF mask.
325        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
326       
327        # Classify bytes for UTF-8 processing, whitespace, control and JSON lexical analysis.
328        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
329       
330        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
331        u8 = u8u16.validate_utf8(u8) 
332       
333        # Mark escape characters
334        escape = parse_escape(lex, EOF_mask)
335       
336#       bitutil.print_aligned_streams([('Input Data', u8data),
337#                             ('escape', bitutil.bitstream2string(escape, lgth)),
338#                             ('DQuote', bitutil.bitstream2string(lex.DQuote, lgth)),
339#                             ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])       
340       
341        # Mark unescaped "
342       
343
344        return
345 
346def demo_parse_json(u8data):
347 
348        global lgth
349        lgth = len(u8data)
350       
351        parse_json(u8data)
352 
353        return
354
355if __name__ == "__main__":
356        import doctest
357        doctest.testmod()
358
359        if len(sys.argv) < 1:
360                sys.stderr.write("Usage: " + filename + "\n")
361                sys.exit(2)
362
363        u8data = bitutil.readfile(sys.argv[1]) 
364#       demo_parse_escape(u8data)
365#       demo_parallel_prefix_parity(u8data)
366#       demo_validate_number(u8data)
367        demo_validate_string(u8data)
368#       demo_parse_json(u8data)
Note: See TracBrowser for help on using the repository browser.