source: proto/JSON/json_prototype.py @ 690

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

Minor milestones.

File size: 16.8 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#def all_starts(u8data):
130#       r"""
131#       
132#       This function returns multi-cursor start positions for each JSON value type.
133#       
134#       """
135#       return (StringStarts, NumberStarts, ArrayStarts, ObjectStarts, TrueStarts, FalseStarts, NullStarts, )
136
137def validate_true_false_null(Lex, EOF_mask):
138        r"""
139        RFC 4627 - JavaScript Object Notation (JSON) 
140
141        true  = %x74.72.75.65      ; true
142        false = %x66.61.6c.73.65   ; false
143        null  = %x6e.75.6c.6c      ; null
144       
145        global lgth
146        lgth = len(u8data)
147        """
148        Errors = 0
149       
150        return Errors
151 
152def demo_true_false_null(u8date):
153        global lgth
154        lgth = len(u8data)
155               
156        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
157        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit) 
158        Errors = validate_true_false_null(Lex, EOF_mask)
159       
160        bitutil.print_aligned_streams([('Input Data', u8data), 
161                              ('Errors', bitutil.bitstream2string(Errors, lgth)),
162                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])       
163        return
164 
165
166def validate_number(Lex, EOF_mask):
167        r"""   
168        RFC 4627 - JavaScript Object Notation (JSON) 
169        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
170
171        number = [ minus ] int [ frac ] [ exp ]
172        decimal-point = %x2E       ; .
173        digit1-9 = %x31-39         ; 1-9
174        e = %x65 / %x45            ; e E
175        exp = e [ minus / plus ] 1*DIGIT
176        frac = decimal-point 1*DIGIT
177        int = zero / ( digit1-9 *DIGIT )
178        minus = %x2D               ; -
179        plus = %x2B                ; +
180        zero = %x30                ; 0 
181        """     
182        Errors = 0
183        M0 = 0                                                  # Initialize marker stream     
184       
185        # WARNING - A hack to set initial cursor positions.
186        ColonCommaLSquareBracket = 0 
187        ColonCommaLSquareBracket = Lex.Colon | Lex.Comma | Lex.LSquareBracket
188        AfterColonCommaLSquareBracket = bitutil.Advance(ColonCommaLSquareBracket)
189        M0 = bitutil.ScanThru(AfterColonCommaLSquareBracket, Lex.WS)
190       
191        M1 = bitutil.ScanThru(M0, Lex.Minus & M0)               # ? Optional character class [-]
192        E1 = M1 &~(Lex.Zero|Lex.Digit1_9)
193
194        M1a = M1 & Lex.Zero                                     # Split
195        M1b = M1 & Lex.Digit0_9                         
196        M2a = bitutil.Advance(M1a)
197        M2b = bitutil.Advance(M1b)
198        M3b = bitutil.ScanThru(M2b,Lex.Digit0_9)
199        M4 = M2a | M3b                                          # Join
200       
201        M4a = M4 &~(Lex.DecimalPoint)                           # Split
202        M4b = M4 & (Lex.DecimalPoint)
203        M5b = bitutil.Advance(M4b)
204        E5b = M5b &~(Lex.Digit0_9)                              # + [0-9]+
205        M6 = bitutil.ScanThru(M5b,Lex.Digit0_9)
206        M7 = M4a | M6                                           # Join
207       
208        M7a = M7 &~(Lex.Ee)                                     # Split
209        # NOTE - Number Follow Set logic is to be handled at a higher level     
210        E7a = M7a &~(Lex.NumberFollowSet)
211        M7b = M7 &(Lex.Ee)
212        M8b = bitutil.Advance(M7b)
213        M9b = bitutil.ScanThru(M8b, Lex.PlusMinus & M8b)        # ? Optional character class [+-]               
214        E9b  = M9b &~(Lex.Digit0_9)                             # + [0-9]+
215        M10b = bitutil.ScanThru(M9b,Lex.Digit0_9)
216        # NOTE - Number Follow Set logic is to be handled at a higher level
217        # E10b = M10b &~(Lex.NumberFollowSet)
218        M11 = M7a | M10b                                        # Join
219       
220        # NOTE - Number Follow Set logic is to be handled at a higher level
221        FollowSetErrors = M11 &~ Lex.NumberFollowSet
222       
223        Errors = E1 | E5b | E9b | FollowSetErrors # E7a | E10b
224       
225        if debug:
226                bitutil.print_aligned_streams([('Input Data', u8data), 
227                              ('M0', bitutil.bitstream2string(M0, lgth)),
228                              ('M1', bitutil.bitstream2string(M1, lgth)),
229                              ('E1', bitutil.bitstream2string(E1, lgth+1)),
230                              ('M1a', bitutil.bitstream2string(M1a, lgth)),
231                              ('M2a', bitutil.bitstream2string(M2a, lgth)),
232                              ('M2b', bitutil.bitstream2string(M2b, lgth)),
233                              ('M3b', bitutil.bitstream2string(M3b, lgth)),
234                              ('M4', bitutil.bitstream2string(M4, lgth)),
235                              ('M4a', bitutil.bitstream2string(M4a, lgth)),
236                              ('M4b', bitutil.bitstream2string(M4b, lgth)),
237                              ('M5b', bitutil.bitstream2string(M5b, lgth)),
238                              ('E5b', bitutil.bitstream2string(E5b, lgth+1)),         
239                              ('M6', bitutil.bitstream2string(M6, lgth)),
240                              ('M7', bitutil.bitstream2string(M7, lgth)),
241                              ('M7a', bitutil.bitstream2string(M7a, lgth)),
242                              #('E7a', bitutil.bitstream2string(E7a, lgth+1)),                                               
243                              ('M7b', bitutil.bitstream2string(M7b, lgth)),
244                              ('M8b', bitutil.bitstream2string(M8b, lgth)),
245                              ('M9b', bitutil.bitstream2string(M9b, lgth)),           
246                              ('E9b', bitutil.bitstream2string(E9b, lgth+1)),         
247                              ('M10b', bitutil.bitstream2string(M10b, lgth)),
248                              #('E10b', bitutil.bitstream2string(E10b, lgth)),
249                              ('M11', bitutil.bitstream2string(M11, lgth)),
250                              ('FollowSetErrors', bitutil.bitstream2string(FollowSetErrors, lgth+1)),                         
251                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])           
252        return Errors
253
254def demo_validate_number(u8data):
255        r"""
256        >>> demo_validate_number('[-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789]')
257        Input Data  : [-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789]
258        Minus       : _1_11_1_____1___1___1____1_______1_______1_________________________
259        Zero        : _________11__11__1___1____1___11___________1______1__1__1__________
260        Digit1_9    : __________________________________111_111____111____1____111111111_
261        Digit0_9    : _________11__11__1___1____1___11__111_111__1_111__1_11__1111111111_
262        DecimalPoint: __________________1___1____1_________1______1______________________
263        Ee          : _______________________1____1______________________1_______________
264        PlusMinus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
265        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111_
266        Errors      : __1_1__1__1___1____1___11___11_1_________1______1_____1__1__________
267        <BLANKLINE>
268
269        >>> demo_validate_number('[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]')
270        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]
271        Minus       : _________________________________1_______________1______________1________________________1__________________________________
272        Zero        : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
273        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_
274        Digit0_9    : _1_1_11_1_11_11_1111_1_1_1_1_1_1__1_1_11_1__11_1__11_1111111111__1111_111111_1_111111111__11_1_111111111__11_11111111111_11_
275        DecimalPoint: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
276        Ee          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
277        PlusMinus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
278        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
279        Errors      : _____________________________________________________________________________________________________________________________
280        <BLANKLINE>
281
282        >>> demo_validate_number('[012345,12345,0,00,-0,-00]')
283        Input Data  : [012345,12345,0,00,-0,-00]
284        Minus       : ___________________1__1___
285        Zero        : _1____________1_11__1__11_
286        Digit1_9    : __11111_11111_____________
287        Digit0_9    : _111111_11111_1_11__1__11_
288        DecimalPoint: __________________________
289        Ee          : __________________________
290        PlusMinus   : ___________________1__1___
291        EOF_Mask    : 11111111111111111111111111_
292        Errors      : __1______________1______1__
293        <BLANKLINE>
294        """ 
295        global lgth
296        lgth = len(u8data)
297
298        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
299        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
300        Errors = validate_number(Lex,EOF_mask)
301
302        bitutil.print_aligned_streams([('Input Data', u8data), 
303                              ('Minus', bitutil.bitstream2string(Lex.Minus, lgth)),
304                              ('Zero', bitutil.bitstream2string(Lex.Zero, lgth)),
305                              ('Digit1_9', bitutil.bitstream2string(Lex.Digit1_9, lgth)),
306                              ('Digit0_9', bitutil.bitstream2string(Lex.Digit0_9, lgth)),
307                              ('DecimalPoint', bitutil.bitstream2string(Lex.DecimalPoint, lgth)),
308                              ('Ee', bitutil.bitstream2string(Lex.Ee, lgth)),
309                              ('PlusMinus', bitutil.bitstream2string(Lex.PlusMinus, lgth)),
310                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
311                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])
312
313def validate_string(Lex,Ctrl,StringMask,EscapeChars,UnescapedDQuotes, lgth):
314        r"""
315        RFC 4627 - JavaScript Object Notation (JSON) 
316
317        string = quotation-mark *char quotation-mark
318        char = unescaped /
319              escape (
320                  %x22 /          ; "    quotation mark  U+0022
321                  %x5C /          ; \    reverse solidus U+005C
322                  %x2F /          ; /    solidus         U+002F
323                  %x62 /          ; b    backspace       U+0008
324                  %x66 /          ; f    form feed       U+000C
325                  %x6E /          ; n    line feed       U+000A
326                  %x72 /          ; r    carriage return U+000D
327                  %x74 /          ; t    tab             U+0009
328                  %x75 4HEXDIG )  ; uXXXX                U+XXXX
329
330        escape = %x5C              ; \
331        quotation-mark = %x22      ; "
332        unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
333
334        JSON string validation requires both:
335        (1) validation of escape characters,
336        (2) validation of unescaped characters.
337        """
338       
339        # (1) Validate escape characters
340        StringEscapeChars = EscapeChars & StringMask
341        Errors = (StringEscapeChars &~ Lex.Escape)
342       
343        u = StringEscapeChars & Lex.u
344       
345        uScope1 = bitutil.Advance(u)
346        uScope2 = bitutil.Advance(uScope1)
347        uScope3 = bitutil.Advance(uScope2)
348        uScope4 = bitutil.Advance(uScope3)
349       
350        Errors |= uScope1 &~ Lex.HexDigit
351        Errors |= uScope2 &~ Lex.HexDigit
352        Errors |= uScope3 &~ Lex.HexDigit
353        Errors |= uScope4 &~ Lex.HexDigit
354       
355        # (2) Validation of unescaped characters
356        # (2.1) StringMask construction ensures all '"' are escaped.
357        # (2.2) '\' are either correctly escaped or the character following an odd length run is escaped.
358        # (2.3) validate_utf8(u8) ensures valid UTF8 encodings in the code point range U+0000 - U+01FFFF. TODO
359
360        StringNotEscapedChars = (~(EscapeChars | Lex.RSolidus)) & StringMask # TODO - Verify logic.
361        Errors |= (StringNotEscapedChars & Ctrl.x00_x1F)
362       
363        # (3) Validate all strings are terminated with an unescaped "
364        StringStarts = StringMask &~ bitutil.Advance(StringMask)
365        StringEnds = bitutil.ScanThru(StringStarts, StringMask)
366        Errors |= StringEnds &~ UnescapedDQuotes
367       
368        if debug:
369                bitutil.print_aligned_streams([('Input Data', u8data), 
370                              ('EscapeChars', bitutil.bitstream2string(EscapeChars, lgth)),
371                              ('StringEscapeChars', bitutil.bitstream2string(StringEscapeChars, lgth)),
372                              ('u', bitutil.bitstream2string(u, lgth)),
373                              ('uScope1', bitutil.bitstream2string(uScope1, lgth)),
374                              ('uScope2', bitutil.bitstream2string(uScope2, lgth)),
375                              ('uScope3', bitutil.bitstream2string(uScope3, lgth)),
376                              ('uScope4', bitutil.bitstream2string(uScope4, lgth)),
377                              ('StringNotEscapedChars', bitutil.bitstream2string(StringNotEscapedChars, lgth)),
378                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])     
379        return Errors
380
381def demo_validate_string(u8data):
382        r"""
383        >>> demo_validate_string('"\u abcd" "\u1___" "\u12__" "\u123_"')
384        Input Data      : "\u abcd" "\u1___" "\u12__" "\u123_"
385        EscapeChars     : __1_________1________1________1_____
386        UnescapedDQuotes: 1_______1_1______1_1______1_1______1
387        ParityMask      : 11111111__1111111__1111111__1111111_
388        StringMask      : _1111111___111111___111111___111111_
389        EOF_Mask        : 111111111111111111111111111111111111_
390        Errors          : ___1__________111_______11________1__
391        <BLANKLINE>
392        """ 
393        global lgth
394        lgth = len(u8data)
395
396        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
397        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
398       
399        # Construct string interior mask (1),(2),(3)
400        # (1) Mark all escaped characters
401        EscapeChars = parse_escape(Lex, EOF_mask)
402       
403        # (2) Mark all unescaped "
404        UnescapedDQuotes = (Lex.DQuote &~ EscapeChars)
405       
406        # (3) Construct mask
407        ParityMask = parallel_prefix_parity(UnescapedDQuotes, lgth) & EOF_mask # TODO - Solve EOF_mask problem
408        StringMask = ParityMask & bitutil.Advance(ParityMask)
409                               
410        Errors = validate_string(Lex,Ctrl,StringMask,EscapeChars, UnescapedDQuotes, lgth)
411       
412        bitutil.print_aligned_streams([('Input Data', u8data), 
413                              ('EscapeChars', bitutil.bitstream2string(EscapeChars, lgth)),
414                              ('UnescapedDQuotes', bitutil.bitstream2string(UnescapedDQuotes, lgth)),
415                              ('ParityMask', bitutil.bitstream2string(ParityMask, lgth)),
416                              ('StringMask', bitutil.bitstream2string(StringMask, lgth)),
417#                             ('StringCursorEnd', bitutil.bitstream2string(StringCursorEnd, lgth+1)),
418                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
419                              ('Errors', bitutil.bitstream2string(Errors, lgth+1))])   
420                             
421        return
422
423def parse_json(u8data):
424 
425        # Transpose to parallel bit streams and prepare an EOF mask.
426        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
427       
428        # Classify bytes for UTF-8 processing, whitespace, control and JSON lexical analysis.
429        (u8, Lex, Ctrl) = byteclass.classify_bytes(bit)
430       
431        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
432        u8 = u8u16.validate_utf8(u8) 
433       
434        # Mark escape characters
435        escape = parse_escape(Lex, EOF_mask)
436       
437        return
438 
439def demo_parse_json(u8data):
440 
441        global lgth
442        lgth = len(u8data)
443       
444        parse_json(u8data)
445 
446        return
447
448if __name__ == "__main__":
449        import doctest
450        doctest.testmod()
451
452        if len(sys.argv) < 2:
453                sys.stderr.write("Usage: python " + filename + " <filename>" "\n")
454                sys.exit(2)
455
456        u8data = bitutil.readfile(sys.argv[1]) 
457#       demo_parse_escape(u8data)
458#       demo_parallel_prefix_parity(u8data)
459#       demo_validate_number(u8data)
460        demo_validate_string(u8data)
461#       demo_parse_json(u8data)
462#       demo_validate_true_false_null(u8data)
Note: See TracBrowser for help on using the repository browser.