From: Eric Mahurin Date: 2005-04-14T14:33:47+09:00 Subject: BNF-like grammar specified DIRECTLY in Ruby --0-371748238-1113456806=:21044 Content-Type: text/plain; charset=us-ascii Content-Id: Content-Disposition: inline Hello everybody, I hope I'm not intruding, but I think I found something you'll like. I think I finally found the holy grail I was looking for in a language - the ability to easily write a readable grammar (BNF-like) directly in the target langauge. I attached a syntax.rb that defines all the classes needed and generic expression evaluator example. The reasons I'm sending this message to the core mailing list is that 1) I want feedback on the API, 2) I think this should be considered for one of the built-in classes (or at least in the standard library) because of its simplicity and power, 3) I have some suggestions for some of the builtin library classes that would help, and 4) some other useful core ruby language suggestions. Here are some of the features of the stuff in syntax.rb: - allows for BNF-like syntax using operators (+: sequence, |: alteration, *: loop, unary +/-: positive/negative lookaheads, ===: compare to a stream) - defaults to inifinite lookahead (using a FLUSH element can control it and where a syntax error is reported) - input stream could contain characters or any type of generic tokens - both a lexer and parser could be written using the same classes - defaults to outputting a parse tree as a multi-level Array structure which can be converted back to the original with simply the to_s method (wasn't overridden). - code can be associated with syntax objects to modify the parse tree, qualify, or do the whole thing - a variety of classes are there for matching atoms: === (character, range, string), includes? (array/string set), [] (array/hash lookup) - although there is no automatic backtracking like regular expressions, you can get some of the same effects with positive/negative lookaheads - everything seems quite straightforward - this a first cut. There are probably bugs. The API probably isn't quite right. Features may be missing. Here are the additions I made to the built-in classes: - added/overrode operator methods to String and Range to automagically create Syntax objects when it seems right. - made Range Comparable. This helped the repeat syntax A*(i..j) be treated like A*i without having to pay attention to whether the multiplier is an integer or a Range. p.s. These are equivalent to A{i,j} and A{i} in regular expressions. - gave keys/values methods to Array so that it can look more like a hash. When an element is false/nil in the array it is consider to not be there for keys/values. Here would be a few more niceties for this syntax stuff if Ruby had these: - Ranges without a end (and/or begin?). If syntactically this is a problem, nil could be used instead. Of course you'd need to raise an exception when you did a bad thing with them (i.e. to_a). For example: (b..)===x -> x>=b (b..).each {} -> infinite loop starting with b (..e)===x -> x<=e (..) ===x -> true - Allow an object to be used like a method. This would require a new operator - I'll call it: (). An object followed by {} or do/end would also be treated the same (that's the part I really want). With this, I could replace the "qualify" method with this thing. Here is an example: class Test; def ()(*args,&code); ... end end a = Test.new a { ... } p.s. I just learned Ruby last week! I really love this language! It's got the best of Perl, C++, and Java. My main complaint is a syntactic one - the use of "end" instead of {}. That's probably the influence of Python. __________________________________ Yahoo! Mail Mobile Take Yahoo! Mail with you! Check email on your mobile phone. http://mobile.yahoo.com/learn/mail --0-371748238-1113456806=:21044 Content-Type: application/octet-stream; name="calc.rb" Content-Transfer-Encoding: base64 Content-Description: calc.rb Content-Disposition: attachment; filename="calc.rb" IyEvdXNyL2Jpbi9ydWJ5IC1kCgpyZXF1aXJlICJzeW50YXgiCgpOVUxMID0g U3ludGF4OjpOVUxMCklORiA9ICsxLjAvMApMT09QMCA9ICgwLi5JTkYpCkxP T1AxID0gKDEuLklORikKCmludCA9ICgoIjAiLi4iOSIpKkxPT1AxKS5xdWFs aWZ5IHsgfG18IG0udG9fcy50b19pIH0KCm51bWJlciA9ICgKICAgIGludCAr CiAgICAoKCIuIitpbnQpfE5VTEwpICsKICAgICgoKCJlInwiRSIpKygiKyJ8 Ii0ifE5VTEwpK2ludCl8TlVMTCkKKS5xdWFsaWZ5IHsgfG18CiAgICBpZiAo bS5sZW5ndGg+MSkKICAgICAgICBtLnRvX3MudG9fZgogICAgZWxzZQogICAg ICAgIG1bMF0KICAgIGVuZAp9Cgp3cyA9ICgoIiAifCJcdCJ8IlxuIikqTE9P UDApLnF1YWxpZnkgeyBUUlVFIH0gIyBza2lwcGVkIHdpdGggVFJVRQoKZXhw ciA9IFN5bnRheDo6UGFzcy5uZXcgIyBuZWVkIHRvIHByZWRlZmluZSBvYmpl Y3QgZm9yIHJlY3Vyc2lvbgoKYXRvbSA9IAogICAgKG51bWJlcit3cykucXVh bGlmeXt8bXxtWzBdfSB8CiAgICAoIigiICsgZXhwciArICIpIiArIHdzKS5x dWFsaWZ5e3xtfG1bMV19Cgp0ZXJtID0gKAogICAgYXRvbSArICggKCIqInwi LyJ8IiUiKSArIHdzICsgYXRvbSApKkxPT1AwCikucXVhbGlmeSB7IHxtfAog ICAgcHJvZHVjdCA9IG1bMF0KICAgIG1bMV0uZWFjaCB7IHxtfAogICAgICAg IGNhc2UgbVswXQogICAgICAgICAgICB3aGVuICIqIiB0aGVuIHByb2R1Y3Qg Kj0gbVsxXQogICAgICAgICAgICB3aGVuICIvIiB0aGVuIHByb2R1Y3QgLz0g bVsxXQogICAgICAgICAgICB3aGVuICIlIiB0aGVuIHByb2R1Y3QgJT0gbVsx XQogICAgICAgIGVuZAogICAgfQogICAgcHJvZHVjdAp9CgpleHByIDw8ICgK ICAgIHdzICsgdGVybSArICggKCIrInwiLSIpICsgd3MgKyB0ZXJtICkqTE9P UDAKKS5xdWFsaWZ5IHsgfG18CiAgICBzdW0gPSBtWzBdCiAgICBtWzFdLmVh Y2ggeyB8bXwKICAgICAgICBjYXNlIG1bMF0KICAgICAgICAgICAgd2hlbiAi KyIgdGhlbiBzdW0gKz0gbVsxXQogICAgICAgICAgICB3aGVuICItIiB0aGVu IHN1bSAtPSBtWzFdCiAgICAgICAgZW5kCiAgICB9CiAgICBzdW0KfQoKd2hp bGUgKGdldHMpCiAgICBwKGV4cHI9PT1SYW5kb21BY2Nlc3NTdHJlYW0ubmV3 KCRfKSkKZW5kCgoKCg== --0-371748238-1113456806=:21044 Content-Type: application/octet-stream; name="syntax.rb" Content-Transfer-Encoding: base64 Content-Description: syntax.rb Content-Disposition: attachment; filename="syntax.rb" CiMgY2xhc3NlcyBpbiB0aGlzIG1vZHVsZSBhbGxvdyBvbmUgdG8gZGVmaW5l IEJORi1saWtlIGdyYW1tYXIgZGlyZWN0bHkgaW4gUnVieQojIEF1dGhvcjog RXJpYyBNYWh1cmluCiMgbGljZW5zZTogZnJlZSwgYnV0IHlvdSBhcmUgYXQg eW91ciBvd24gcmlzayBpZiB5b3UgdXNlIGl0Cgptb2R1bGUgU3ludGF4Cgog ICAgIyBiYXNlIGNsYXNzIHdoZXJlIGNvbW1vbiBvcGVyYXRvcnMgYXJlIGRl ZmluZWQKICAgIGNsYXNzIEJhc2UKICAgICAgICBkZWYgfChvdGhlcikKICAg ICAgICAgICAgQWx0ZXJhdGlvbi5uZXcoc2VsZixvdGhlcikKICAgICAgICBl bmQKICAgICAgICBkZWYgKyhvdGhlcikKICAgICAgICAgICAgU2VxdWVuY2Uu bmV3KHNlbGYsb3RoZXIpCiAgICAgICAgZW5kCiAgICAgICAgZGVmICoobXVs dGlwbGllcikKICAgICAgICAgICAgUmVwZWF0Lm5ldyhzZWxmLG11bHRpcGxp ZXIpCiAgICAgICAgZW5kCiAgICAgICAgZGVmICtACiAgICAgICAgICAgIFBv c2l0aXZlLm5ldyhzZWxmKQogICAgICAgIGVuZAogICAgICAgIGRlZiAtQAog ICAgICAgICAgICBOZWdhdGl2ZS5uZXcoc2VsZikKICAgICAgICBlbmQKICAg ICAgICBkZWYgcXVhbGlmeSgqYXJncywmY29kZSkKICAgICAgICAgICAgUXVh bGlmeS5uZXcoc2VsZiwqYXJncywmY29kZSkKICAgICAgICBlbmQKICAgIGVu ZAoKICAgICMganVzdCBwYXNzZXMgdGhlIHN5bnRheCB0aHJvdWdoIC0gbmVl ZGVkIGZvciByZWN1cnNpdmUgc3ludGF4CiAgICBjbGFzcyBQYXNzIDwgQmFz ZQogICAgICAgIGRlZiBpbml0aWFsaXplKHN5bnRheD1OVUxMKQogICAgICAg ICAgICBAc3ludGF4ID0KICAgICAgICAgICAgICAgIGlmIChzeW50YXgua2lu ZF9vZj9CYXNlKQogICAgICAgICAgICAgICAgICAgIHN5bnRheAogICAgICAg ICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIFZlcmJhdGltLm5l dyhzeW50YXgpCiAgICAgICAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAg ICAgICBkZWYgPDwoc3ludGF4KQogICAgICAgICAgICBpbml0aWFsaXplKHN5 bnRheCkKICAgICAgICBlbmQKICAgICAgICBkZWYgPT09KHN0cmVhbSkKICAg ICAgICAgICAgQHN5bnRheD09PXN0cmVhbQogICAgICAgIGVuZAogICAgZW5k CiAgICAKICAgICMgZ2VuZXJpYyBjb2RlIG1hdGNoZXMgdG8gdGhlIHN0cmVh bSAoZmlyc3QgYXJnIHRvIHRoZSBjb2RlKQogICAgIyBbXSBvcGVyYXRvciBh bGxvd3MgYWRkaXRpb25hbCBhcmd1bWVudHMgdG8gYmUgcGFzc2VkIHRvIHRo ZSBjb2RlCiAgICBjbGFzcyBDb2RlIDwgQmFzZQogICAgICAgIGRlZiBpbml0 aWFsaXplKCphcmdzLCZjb2RlKQogICAgICAgICAgICBAYXJncyA9IGFyZ3MK ICAgICAgICAgICAgQGNvZGUgPSBjb2RlCiAgICAgICAgZW5kCiAgICAgICAg ZGVmID09PShzdHJlYW0sKmFyZ3MpICMgcGFzc2luZyBhcmdzIGhlcmUgd2ls bCBieXBhc3MgY3JlYXRpbmcgYSBuZXcgb2JqZWN0CiAgICAgICAgICAgICht YXRjaCA9IEBjb2RlW3N0cmVhbSwqKEBhcmdzK2FyZ3MpXSkgfHwKICAgICAg ICAgICAgICAgc3RyZWFtLmJ1ZmZlcmVkIHx8IHJhaXNlKEVycm9yLm5ldyhz dHJlYW0sImEgc2VtYW50aWMgZXJyb3IiKSkKICAgICAgICAgICAgbWF0Y2gK ICAgICAgICBlbmQKICAgICAgICBkZWYgW10oKmFyZ3MpCiAgICAgICAgICAg IHNlbGYuY2xhc3MubmV3KCooQGFyZ3MrYXJncyksJkBjb2RlKQogICAgICAg IGVuZAogICAgZW5kCgogICAgIyBxdWFsaWZ5IHRoZSBtYXRjaCB3aXRoIHNv bWUgY29kZSB0aGF0IHRha2VzIHRoZSBtYXRjaAogICAgIyBbXSBvcGVyYXRv ciBhbGxvd3MgYWRkaXRpb25hbCBhcmd1bWVudHMgdG8gYmUgcGFzc2VkIHRv IHRoZSBjb2RlCiAgICBjbGFzcyBRdWFsaWZ5IDwgQmFzZQogICAgICAgIGRl ZiBpbml0aWFsaXplKHN5bnRheD1OVUxMLCphcmdzLCZjb2RlKQogICAgICAg ICAgICBAc3ludGF4ID0KICAgICAgICAgICAgICAgIGlmIChzeW50YXgua2lu ZF9vZj9CYXNlKQogICAgICAgICAgICAgICAgICAgIHN5bnRheAogICAgICAg ICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIFZlcmJhdGltLm5l dyhzeW50YXgpCiAgICAgICAgICAgICAgICBlbmQKICAgICAgICAgICAgQGFy Z3MgPSBhcmdzCiAgICAgICAgICAgIEBjb2RlID0gY29kZQogICAgICAgIGVu ZAogICAgICAgIGRlZiA9PT0oc3RyZWFtLCphcmdzKSAjIHBhc3NpbmcgYXJn cyBoZXJlIHdpbGwgYnlwYXNzIGNyZWF0aW5nIGEgbmV3IG9iamVjdAogICAg ICAgICAgICAobWF0Y2ggPSAoQHN5bnRheD09PXN0cmVhbSkpIHx8IChyZXR1 cm4gbWF0Y2gpCiAgICAgICAgICAgIChtYXRjaCA9IEBjb2RlW21hdGNoLCoo QGFyZ3MrYXJncyldKSB8fAogICAgICAgICAgICAgICBzdHJlYW0uYnVmZmVy ZWQgfHwgcmFpc2UoRXJyb3IubmV3KHN0cmVhbSwiYSBzZW1hbnRpYyBxdWFs aWZpY2F0aW9uIGVycm9yIikpCiAgICAgICAgICAgIG1hdGNoCiAgICAgICAg ZW5kCiAgICAgICAgZGVmIFtdKCphcmdzKQogICAgICAgICAgICBzZWxmLmNs YXNzLm5ldyhAc3ludGF4LCooQGFyZ3MrYXJncyksJkBjb2RlKQogICAgICAg IGVuZAogICAgZW5kCgogICAgIyBzZXF1ZW5jZSBvZiBzeW50YXhlcwogICAg Y2xhc3MgU2VxdWVuY2UgPCBCYXNlCiAgICAgICAgZGVmIGluaXRpYWxpemUo KnN5bnRheGVzKQogICAgICAgICAgICBAc3ludGF4ID0gc3ludGF4ZXMuY29s bGVjdCBkbyB8c3ludGF4fAogICAgICAgICAgICAgICAgaWYgKHN5bnRheC5r aW5kX29mP0Jhc2UpCiAgICAgICAgICAgICAgICAgICAgc3ludGF4CiAgICAg ICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgVmVyYmF0aW0u bmV3KHN5bnRheCkKICAgICAgICAgICAgICAgIGVuZAogICAgICAgICAgICBl bmQKICAgICAgICBlbmQKICAgICAgICBkZWYgKyhvdGhlcikKICAgICAgICAg ICAgc2VsZi5jbGFzcy5uZXcoKihAc3ludGF4K1tvdGhlcl0pKSAjIHB1bGwg aW4gbXVsdGlwbGUgc2VxdWVuY2UgaXRlbXMKICAgICAgICBlbmQKICAgICAg ICBkZWYgPDwob3RoZXIpCiAgICAgICAgICAgIEBzeW50YXggPDwgKChvdGhl ci5raW5kX29mP0Jhc2UpP290aGVyOlZlcmJhdGltLm5ldyhvdGhlcikpCiAg ICAgICAgZW5kCiAgICAgICAgZGVmID09PShzdHJlYW0pCiAgICAgICAgICAg IG1hdGNoZXMgPSBbXQogICAgICAgICAgICBAc3ludGF4LmVhY2ggZG8gfHN5 bnRheHwKICAgICAgICAgICAgICAgIG1hdGNoID0gKHN5bnRheD09PXN0cmVh bSkKICAgICAgICAgICAgICAgIGlmICghbWF0Y2gpCiAgICAgICAgICAgICAg ICAgICAgbWF0Y2hlcz1OSUwKICAgICAgICAgICAgICAgICAgICBicmVhawog ICAgICAgICAgICAgICAgZW5kCiAgICAgICAgICAgICAgICBtYXRjaGVzIDw8 IG1hdGNoIGlmIG1hdGNoIT1UUlVFCiAgICAgICAgICAgIGVuZAogICAgICAg ICAgICBtYXRjaGVzCiAgICAgICAgZW5kCiAgICBlbmQKCiAgICAjIGFsdGVy bmF0aXZlIHN5bnRheGVzCiAgICBjbGFzcyBBbHRlcmF0aW9uIDwgQmFzZQog ICAgICAgIGRlZiBpbml0aWFsaXplKCpzeW50YXhlcykKICAgICAgICAgICAg QHN5bnRheCA9IHN5bnRheGVzLmNvbGxlY3QgZG8gfHN5bnRheHwKICAgICAg ICAgICAgICAgIGlmIChzeW50YXgua2luZF9vZj9CYXNlKQogICAgICAgICAg ICAgICAgICAgIHN5bnRheAogICAgICAgICAgICAgICAgZWxzZQogICAgICAg ICAgICAgICAgICAgIFZlcmJhdGltLm5ldyhzeW50YXgpCiAgICAgICAgICAg ICAgICBlbmQKICAgICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICAgICAg ZGVmIHwob3RoZXIpCiAgICAgICAgICAgIHNlbGYuY2xhc3MubmV3KCooQHN5 bnRheCtbb3RoZXJdKSkgIyBwdWxsIGluIG11bHRpcGxlIGFsdGVyYXRpb24g aXRlbXMKICAgICAgICBlbmQKICAgICAgICBkZWYgPDwob3RoZXIpCiAgICAg ICAgICAgIEBzeW50YXggPDwgKChvdGhlci5raW5kX29mP0Jhc2UpP290aGVy OlZlcmJhdGltLm5ldyhvdGhlcikpCiAgICAgICAgZW5kCiAgICAgICAgZGVm ID09PShzdHJlYW0pCiAgICAgICAgICAgIG1hdGNoID0gbmlsCiAgICAgICAg ICAgIEBzeW50YXguZGV0ZWN0IGRvIHxzeW50YXh8CiAgICAgICAgICAgICAg ICBtYXRjaCA9IHN0cmVhbS5idWZmZXIgeyB8c3RyZWFtfCBzeW50YXg9PT1z dHJlYW0gfQogICAgICAgICAgICBlbmQKICAgICAgICAgICAgbWF0Y2ggfHwg c3RyZWFtLmJ1ZmZlcmVkIHx8IHJhaXNlKEVycm9yLm5ldyhzdHJlYW0sbmls LCJhbiBhbHRlcmF0aW9uIikpCiAgICAgICAgICAgIG1hdGNoCiAgICAgICAg ZW5kCiAgICAgICAgYWxpYXMgPX4gPT09CiAgICBlbmQKCiAgICAjIHJlcGVh dGluZyBzeW50YXgKICAgIGNsYXNzIFJlcGVhdCA8IEJhc2UKICAgICAgICBk ZWYgaW5pdGlhbGl6ZShzeW50YXgsbXVsdGlwbGllcikKICAgICAgICAgICAg QHN5bnRheCA9CiAgICAgICAgICAgICAgICBpZiAoc3ludGF4LmtpbmRfb2Y/ QmFzZSkKICAgICAgICAgICAgICAgICAgICBzeW50YXgKICAgICAgICAgICAg ICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBWZXJiYXRpbS5uZXcoc3lu dGF4KQogICAgICAgICAgICAgICAgZW5kCiAgICAgICAgICAgIEByZXBlYXQg PQogICAgICAgICAgICAgICAgaWYgKG11bHRpcGxpZXIua2luZF9vZj9Qcm9j KQogICAgICAgICAgICAgICAgICAgIG11bHRpcGxpZXIKICAgICAgICAgICAg ICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBsYW1iZGEgZG8gfG1hdGNo ZXN8CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbXBhcmUgPSAobXVsdGlw bGllcjw9PihtYXRjaGVzLmxlbmd0aCsxKSkKICAgICAgICAgICAgICAgICAg ICAgICAgaWYgKGNvbXBhcmU9PTApCiAgICAgICAgICAgICAgICAgICAgICAg ICAgICBjb21wYXJlID0gKG11bHRpcGxpZXI8PT5tYXRjaGVzLmxlbmd0aCkK ICAgICAgICAgICAgICAgICAgICAgICAgZW5kCiAgICAgICAgICAgICAgICAg ICAgICAgIGNvbXBhcmUKICAgICAgICAgICAgICAgICAgICBlbmQKICAgICAg ICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgICAgIGRlZiA9PT0oc3Ry ZWFtKQogICAgICAgICAgICBtYXRjaGVzID0gW10KICAgICAgICAgICAgd2hp bGUgKChjb21wYXJlPUByZXBlYXRbbWF0Y2hlc10pPj0wKQogICAgICAgICAg ICAgICAgaWYgKGNvbXBhcmU+MCkKICAgICAgICAgICAgICAgICAgICB1bmxl c3MgKG1hdGNoID0gKEBzeW50YXg9PT1zdHJlYW0pKQogICAgICAgICAgICAg ICAgICAgICAgICByZXR1cm4gTklMCiAgICAgICAgICAgICAgICAgICAgZW5k CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgdW5s ZXNzIChtYXRjaCA9IHN0cmVhbS5idWZmZXIgeyB8c3RyZWFtfCBAc3ludGF4 PT09c3RyZWFtIH0pCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrCiAg ICAgICAgICAgICAgICAgICAgZW5kCiAgICAgICAgICAgICAgICBlbmQKICAg ICAgICAgICAgICAgIG1hdGNoZXMgPDwgbWF0Y2gKICAgICAgICAgICAgZW5k CiAgICAgICAgICAgICMgZmlsdGVyIG91dCBzaW1wbGUgVFJVRSBlbGVtZW50 cwogICAgICAgICAgICBtYXRjaGVzID0gbWF0Y2hlcy5maW5kX2FsbCB7IHxt YXRjaHwgbWF0Y2ghPVRSVUUgfQogICAgICAgICAgICBtYXRjaGVzCiAgICAg ICAgZW5kCiAgICBlbmQKICAgIAogICAgIyBwb3NpdGl2ZSBzeW50YWN0aWMg cHJlZGljYXRlCiAgICBjbGFzcyBQb3NpdGl2ZSA8IEJhc2UKICAgICAgICBk ZWYgaW5pdGlhbGl6ZShzeW50YXgpCiAgICAgICAgICAgIEBzeW50YXggPQog ICAgICAgICAgICAgICAgaWYgKHN5bnRheC5raW5kX29mP0Jhc2UpCiAgICAg ICAgICAgICAgICAgICAgc3ludGF4CiAgICAgICAgICAgICAgICBlbHNlCiAg ICAgICAgICAgICAgICAgICAgVmVyYmF0aW0ubmV3KHN5bnRheCkKICAgICAg ICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgICAgIGRlZiA9PT0oc3Ry ZWFtKQogICAgICAgICAgICBzdHJlYW0uYnVmZmVyIHsgfHN0cmVhbXwgbWF0 Y2ggPSAoQHN5bnRheD09PXN0cmVhbSk7IEZBTFNFIH0KICAgICAgICAgICAg aWYgKG1hdGNoKQogICAgICAgICAgICAgICAgVFJVRQogICAgICAgICAgICBl bHNlCiAgICAgICAgICAgICAgICBzdHJlYW0uYnVmZmVyZWQgfHwgcmFpc2Uo RXJyb3IubmV3KHN0cmVhbSxuaWwsImEgcG9zaXRpdmUgc3ludGF0aWMgcHJl ZGljYXRlIikpCiAgICAgICAgICAgICAgICBGQUxTRQogICAgICAgICAgICBl bmQKICAgICAgICBlbmQKICAgIGVuZAoKICAgICMgbmVnYXRpdmUgc3ludGFj dGljIHByZWRpY2F0ZQogICAgY2xhc3MgTmVnYXRpdmUgPCBQb3NpdGl2ZQog ICAgICAgIGRlZiA9PT0oc3RyZWFtKQogICAgICAgICAgICBzdHJlYW0uYnVm ZmVyIHsgfHN0cmVhbXwgbWF0Y2ggPSAoQHN5bnRheD09PXN0cmVhbSk7IEZB TFNFIH0KICAgICAgICAgICAgaWYgKCFtYXRjaCkKICAgICAgICAgICAgICAg IFRSVUUKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgc3RyZWFt LmJ1ZmZlcmVkIHx8IHJhaXNlKEVycm9yLm5ldyhzdHJlYW0sbmlsLCJhIG5l Z2F0aXZlIHN5bnRhdGljIHByZWRpY2F0ZSIpKQogICAgICAgICAgICAgICAg RkFMU0UKICAgICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICBlbmQKCiAg ICAjIGFsbCBhdG9tcyBjYW4gYWxzbyB1c2UgfiB0byBpbnZlcnQgd2hhdCdz IG1hdGNoZXMKCiAgICAjIGVsZW1lbnQgbWF0Y2ggKHVzZXMgPT09IHRvIG1h dGNoKQogICAgY2xhc3MgQXRvbSA8IEJhc2UKICAgICAgICBkZWYgaW5pdGlh bGl6ZShwYXR0ZXJuLGxlbmd0aD1OSUwsaW52ZXJ0PUZBTFNFKQogICAgICAg ICAgICBAcGF0dGVybiA9IHBhdHRlcm4KICAgICAgICAgICAgQGxlbmd0aCA9 IGxlbmd0aAogICAgICAgICAgICBAaW52ZXJ0ID0gaW52ZXJ0CiAgICAgICAg ZW5kCiAgICAgICAgZGVmIH5ACiAgICAgICAgICAgIG5ldyhwYXR0ZXJuLGxl bmd0aCwhaW52ZXJ0KQogICAgICAgIGVuZAogICAgICAgIGRlZiA9PT0oc3Ry ZWFtKQogICAgICAgICAgICBlbGVtZW50ID0gc3RyZWFtLmdldChAbGVuZ3Ro KQogICAgICAgICAgICBtYXRjaCA9IChAcGF0dGVybj09PWVsZW1lbnQpCiAg ICAgICAgICAgIG1hdGNoID0gIW1hdGNoIGlmIChAaW52ZXJ0KQogICAgICAg ICAgICBpZiAobWF0Y2g9PVRSVUUpCiAgICAgICAgICAgICAgICBlbGVtZW50 IHx8IFRSVUUKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgbWF0 Y2ggfHwgYmVnaW4KICAgICAgICAgICAgICAgICAgICBzdHJlYW0uYnVmZmVy ZWQgfHwgcmFpc2UoRXJyb3IubmV3KHN0cmVhbSxlbGVtZW50Lmluc3BlY3Qs QHBhdHRlcm4uaW5zcGVjdCkpCiAgICAgICAgICAgICAgICAgICAgRkFMU0UK ICAgICAgICAgICAgICAgIGVuZAogICAgICAgICAgICBlbmQKICAgICAgICBl bmQKICAgIGVuZAogICAgCiAgICAjIGVsZW1lbnQgc2V0ICh1c2VzIGluY2x1 ZGU/IHRvIG1hdGNoKQogICAgY2xhc3MgU2V0IDwgQXRvbQogICAgICAgIGRl ZiA9PT0oc3RyZWFtKQogICAgICAgICAgICBlbGVtZW50ID0gc3RyZWFtLmdl dChAbGVuZ3RoKQogICAgICAgICAgICBtYXRjaCA9IEBwYXR0ZXJuLmluY2x1 ZGU/KGVsZW1lbnQpCiAgICAgICAgICAgIG1hdGNoID0gIW1hdGNoIGlmIChA aW52ZXJ0KQogICAgICAgICAgICBpZiAobWF0Y2g9PVRSVUUpCiAgICAgICAg ICAgICAgICBlbGVtZW50IHx8IFRSVUUKICAgICAgICAgICAgZWxzZQogICAg ICAgICAgICAgICAgbWF0Y2ggfHwgYmVnaW4KICAgICAgICAgICAgICAgICAg ICBzdHJlYW0uYnVmZmVyZWQgfHwgcmFpc2UoRXJyb3IubmV3KHN0cmVhbSxl bGVtZW50Lmluc3BlY3QsIm9uZSBvZiB0aGVzZTogI3tAcGF0dGVybi50b19z fSIpKQogICAgICAgICAgICAgICAgICAgIEZBTFNFCiAgICAgICAgICAgICAg ICBlbmQKICAgICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICBlbmQKICAg IAogICAgIyBlbGVtZW50IGxvb2t1cCBhcnJheSBvciBoYXNoICh1c2VzIFtd IHRvIG1hdGNoKQogICAgIyB0cmFuc2xhdGlvbiB3aWxsIG9jY3VyIGlmIHRo ZSBsb29rdXAgcmV0dXJucyBhbnl0aGluZyBidXQgVFJVRQogICAgY2xhc3Mg TG9va3VwIDwgQXRvbQogICAgICAgIGRlZiA9fihzdHJlYW0pCiAgICAgICAg ICAgIGVsZW1lbnQgPSBzdHJlYW0uZ2V0KEBsZW5ndGgpCiAgICAgICAgICAg IG1hdGNoID0gQHBhdHRlcm5bZWxlbWVudF0KICAgICAgICAgICAgbWF0Y2gg PSAhbWF0Y2ggaWYgKEBpbnZlcnQpCiAgICAgICAgICAgIGlmIChtYXRjaD09 VFJVRSkKICAgICAgICAgICAgICAgIGVsZW1lbnQgfHwgVFJVRQogICAgICAg ICAgICBlbHNlCiAgICAgICAgICAgICAgICBtYXRjaCB8fCBiZWdpbgogICAg ICAgICAgICAgICAgICAgIHN0cmVhbS5idWZmZXJlZCB8fCByYWlzZShFcnJv ci5uZXcoc3RyZWFtLGVsZW1lbnQuaW5zcGVjdCwib25lIG9mIHRoZXNlOiAj e0BwYXR0ZXJuLmtleXMudG9fc30iKSkKICAgICAgICAgICAgICAgICAgICBG QUxTRQogICAgICAgICAgICAgICAgZW5kCiAgICAgICAgICAgIGVuZAogICAg ICAgIGVuZAogICAgZW5kCiAgICAKICAgICMgZWxlbWVudCBzZXF1ZW5jZSB0 aGF0IGtub3dzIGl0cyBsZW5ndGgKICAgIGNsYXNzIFZlcmJhdGltIDwgQXRv bQogICAgICAgIGRlZiBpbml0aWFsaXplKHBhdHRlcm4saW52ZXJ0PUZBTFNF KQogICAgICAgICAgICBAcGF0dGVybiA9IHBhdHRlcm4KICAgICAgICAgICAg QGludmVydCA9IGludmVydAogICAgICAgIGVuZAogICAgICAgIGRlZiB+QAog ICAgICAgICAgICBuZXcocGF0dGVybiwhaW52ZXJ0KQogICAgICAgIGVuZAog ICAgICAgIGRlZiA9PT0oc3RyZWFtKQogICAgICAgICAgICBlbGVtZW50ID0g c3RyZWFtLmdldChAcGF0dGVybi5sZW5ndGgpCiAgICAgICAgICAgIGlmIChl bGVtZW50KQogICAgICAgICAgICAgICAgbWF0Y2ggPSAoQHBhdHRlcm49PT1l bGVtZW50KQogICAgICAgICAgICAgICAgbWF0Y2ggPSAhbWF0Y2ggaWYgKEBp bnZlcnQpCiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIG1hdGNo ID0gRkFMU0UKICAgICAgICAgICAgZW5kCiAgICAgICAgICAgIGlmIChtYXRj aD09VFJVRSkKICAgICAgICAgICAgICAgIGVsZW1lbnQgfHwgVFJVRQogICAg ICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBtYXRjaCB8fCBiZWdpbgog ICAgICAgICAgICAgICAgICAgIHN0cmVhbS5idWZmZXJlZCB8fCByYWlzZShF cnJvci5uZXcoc3RyZWFtLGVsZW1lbnQuaW5zcGVjdCxAcGF0dGVybi5pbnNw ZWN0KSkKICAgICAgICAgICAgICAgICAgICBGQUxTRQogICAgICAgICAgICAg ICAgZW5kCiAgICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgZW5kCgog ICAgIyBhbnkgZWxlbWVudAogICAgY2xhc3MgQW55IDwgQXRvbQogICAgICAg IGRlZiBpbml0aWFsaXplKGxlbmd0aD1OSUwsaW52ZXJ0PUZBTFNFKQogICAg ICAgICAgICBAbGVuZ3RoID0gbGVuZ3RoCiAgICAgICAgICAgIEBpbnZlcnQg PSBpbnZlcnQKICAgICAgICBlbmQKICAgICAgICBkZWYgfkAgIyBjcmVhdGUg YSBuZXZlciBtYXRjaGluZyBBdG9tCiAgICAgICAgICAgIG5ldyhsZW5ndGgs IWludmVydCkKICAgICAgICBlbmQKICAgICAgICBkZWYgPT09KHN0cmVhbSkK ICAgICAgICAgICAgZWxlbWVudCA9IHN0cmVhbS5nZXQoQGxlbmd0aCkKICAg ICAgICAgICAgIUBpbnZlcnQgJiYgZWxlbWVudAogICAgICAgIGVuZAogICAg ZW5kCiAgICBBTlkgPSBBbnkubmV3CiAgICAKCiAgICAjIHplcm8gbGVuZ3Ro IGNvbnN0YW50cwogICAgRkxVU0ggPSBDb2RlLm5ldyB7IHxzdHJlYW18IHN0 cmVhbS5mbHVzaDsgVFJVRSB9CiAgICBGQUlMID0gQ29kZS5uZXcgeyBGQUxT RSB9CiAgICBOVUxMID0gQ29kZS5uZXcgeyBUUlVFIH0KICAgIE5VTExTID0g Q29kZS5uZXcgeyBbXSB9CiAgICBFT0YgPSBDb2RlLm5ldyB7ICEoZWxlbWVu dCA9IHN0cmVhbS5nZXQpIH0KCiAgICAjIGV4Y2VwdGlvbiBjbGFzcyBmb3Ig aGFuZGxpbmcgc3ludGF4IGVycm9ycwogICAgY2xhc3MgRXJyb3IgPCBSdW50 aW1lRXJyb3IKICAgICAgICBhdHRyX2FjY2Vzc29yKDpzdHJlYW0sOmZvdW5k LDpleHBlY3RlZCkKICAgICAgICBkZWYgaW5pdGlhbGl6ZShzdHJlYW09bmls LGZvdW5kPW5pbCxleHBlY3RlZD1uaWwpCiAgICAgICAgICAgIEBzdHJlYW0g PSBzdHJlYW0KICAgICAgICAgICAgQGZvdW5kID0gZm91bmQKICAgICAgICAg ICAgQGV4cGVjdGVkID0gZXhwZWN0ZWQKICAgICAgICBlbmQKICAgICAgICBk ZWYgdG9fcwogICAgICAgICAgICBlcnIgPSBbc3VwZXJdCiAgICAgICAgICAg IGVyciA8PCAiZm91bmQgI3tmb3VuZC50b19zfSIgaWYgZm91bmQKICAgICAg ICAgICAgZXJyIDw8ICJleHBlY3RlZCAje2V4cGVjdGVkLnRvX3N9IiBpZiBl eHBlY3RlZAogICAgICAgICAgICBlcnIgPDwgc3RyZWFtLmxvY2F0aW9uLnRv X3MgaWYgc3RyZWFtCiAgICAgICAgICAgIGVyciAqICIsICIKICAgICAgICBl bmQKICAgIGVuZAoKZW5kCgoKIyBjbGFzcyBhY3RzIGxpa2UgYW4gaXRlcmF0 b3Igb3ZlciBhIHN0cmluZy9hcnJheS9ldGMKIyBleGNlcHQgdGhhdCB1c2lu ZyBidWZmZXIgYWxsb3dzIG9uZSBnbyBiYWNrIHRvIGEgY2VydGFpbiBwb2lu dAojIGFub3RoZXIgY2xhc3MgY291bGQgYmUgZGVzaWduZWQgdG8gd29yayBv biBhbiBJTy9GaWxlCmNsYXNzIFJhbmRvbUFjY2Vzc1N0cmVhbQogICAgZGVm IGluaXRpYWxpemUocyxwb3M9MCkKICAgICAgICBAcyA9IHMKICAgICAgICBA cG9zID0gcG9zCiAgICAgICAgQGJ1ZmZlcmVkID0gTklMCiAgICAgICAgc2Vs ZgogICAgZW5kCiAgICBkZWYgZ2V0KHRlcm1pbmF0aW9uPU5JTCkKICAgICAg ICBpZiAoQHBvcz49QHMubGVuZ3RoKQogICAgICAgICAgICAjIGVuZCBvZiBm aWxlL3N0cmluZy9hcnJheQogICAgICAgICAgICBlbGVtZW50ID0gTklMCiAg ICAgICAgZWxzaWYgKCF0ZXJtaW5hdGlvbikKICAgICAgICAgICAgIyByZWFk IG9uZSBjaGFyYWN0ZXIvZWxlbWVudAogICAgICAgICAgICBlbGVtZW50ID0g QHNbQHBvc10KICAgICAgICAgICAgQHBvcyArPSAxCiAgICAgICAgZWxzZQog ICAgICAgICAgICAjIHJlYWQgYSBzdWItc3RyaW5nL3N1Yi1hcnJheQogICAg ICAgICAgICBwb3MxID0gKHRlcm1pbmF0aW9uLmtpbmRfb2Y/KEludGVnZXIp KSA/IEBwb3MrdGVybWluYXRpb24gOgogICAgICAgICAgICAgICAgICAgKHQg PSBAcy5pbmRleCh0ZXJtaW5hdGlvbixAcG9zKSkgPyB0K3Rlcm1pbmF0aW9u Lmxlbmd0aCA6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICBAcy5sZW5ndGgKICAgICAgICAgICAgZWxlbWVudCA9IEBz W0Bwb3MuLi5wb3MxXQogICAgICAgICAgICBAcG9zID0gcG9zMQogICAgICAg IGVuZAogICAgICAgIGVsZW1lbnQKICAgIGVuZAogICAgZGVmIGJ1ZmZlcigm Y29kZSkKICAgICAgICBvbGRfYnVmZmVyZWQgPSBAYnVmZmVyZWQKICAgICAg ICBAYnVmZmVyZWQgPSBAcG9zIGlmICghQGJ1ZmZlcmVkIHx8IEBwb3M8QGJ1 ZmZlcmVkKQogICAgICAgIHBvcyA9IEBwb3MKICAgICAgICBtYXRjaCA9IE5J TAogICAgICAgIG1hdGNoID0gY29kZVtzZWxmXQogICAgICAgIGlmIChAYnVm ZmVyZWQgJiYgQGJ1ZmZlcmVkPD1wb3MpCiAgICAgICAgICAgIEBidWZmZXJl ZCA9IG9sZF9idWZmZXJlZAogICAgICAgIGVsc2lmICghbWF0Y2gpCiAgICAg ICAgICAgIHJhaXNlKEluZGV4RXJyb3IsIm5lZWQgdG8gcmV3aW5kIGJ1ZmZl ciwgYnV0IGl0IHdhcyBmbHVzaGVkIikKICAgICAgICBlbmQKICAgICAgICBA cG9zID0gcG9zIGlmICFtYXRjaAogICAgICAgIG1hdGNoCiAgICBlbmQKICAg IGRlZiBmbHVzaAogICAgICAgIEBidWZmZXJlZCA9IE5JTAogICAgZW5kCiAg ICBkZWYgYnVmZmVyZWQKICAgICAgICBAYnVmZmVyZWQgPyBUUlVFIDogRkFM U0UKICAgIGVuZAogICAgZGVmIGxvY2F0aW9uCiAgICAgICAgImluZGV4ICN7 QHBvc30gaW4gI3tAcy5pbnNwZWN0fSIKICAgIGVuZAplbmQKCgojIHB1dCBz dHVmZiBpbiBTdHJpbmcgdG8gaGF2ZSBTeW50YXggb2JqZWN0cyBtYWdpY2Fs bHkgYXBwZWFyCmNsYXNzIFN0cmluZwogICAgZGVmIHwob3RoZXIpCiAgICAg ICAgU3ludGF4OjpWZXJiYXRpbS5uZXcoc2VsZil8b3RoZXIKICAgIGVuZAog ICAgZGVmICtACiAgICAgICAgK1N5bnRheDo6VmVyYmF0aW0ubmV3KHNlbGYp CiAgICBlbmQKICAgIGRlZiAtQAogICAgICAgIC1TeW50YXg6OlZlcmJhdGlt Lm5ldyhzZWxmKQogICAgZW5kCiAgICBhbGlhcyBfcmVwZWF0ICoKICAgIGRl ZiAqKG90aGVyKQogICAgICAgIGlmIChvdGhlci5raW5kX29mP051bWVyaWMp CiAgICAgICAgICAgIF9yZXBlYXQob3RoZXIpCiAgICAgICAgZWxzZQogICAg ICAgICAgICBTeW50YXg6OlZlcmJhdGltLm5ldyhzZWxmKSpvdGhlcgogICAg ICAgIGVuZAogICAgZW5kCiAgICBhbGlhcyBfY29uY2F0ICsKICAgIGRlZiAr KG90aGVyKQogICAgICAgIGlmIChvdGhlci5raW5kX29mP1N0cmluZykKICAg ICAgICAgICAgX2NvbmNhdChvdGhlcikKICAgICAgICBlbHNlCiAgICAgICAg ICAgIFN5bnRheDo6VmVyYmF0aW0ubmV3KHNlbGYpK290aGVyCiAgICAgICAg ZW5kCiAgICBlbmQKICAgIGRlZiA9PT0ob3RoZXIpCiAgICAgICAgaWYgKG90 aGVyLmtpbmRfb2Y/U3RyaW5nKQogICAgICAgICAgICBzZWxmPT1vdGhlcgog ICAgICAgIGVsc2UKICAgICAgICAgICAgU3ludGF4OjpWZXJiYXRpbS5uZXco c2VsZik9PT1vdGhlcgogICAgICAgIGVuZAogICAgZW5kCiAgICBkZWYgcXVh bGlmeSgmY29kZSkKICAgICAgICBTeW50YXg6OlZlcmJhdGltLm5ldyhzZWxm KS5xdWFsaWZ5KCZjb2RlKQogICAgZW5kCmVuZAoKIyBhbGxvdyBhbiBBcnJh eSB0byBsb29rIG1vcmUgbGlrZSBhIEhhc2ggd2l0aCBrZXlzIGFuZCB2YWx1 ZXMKY2xhc3MgQXJyYXkKICAgIGRlZiBrZXlzCiAgICAgICAgKDAuLi5sZW5n dGgpLmZpbmRfYWxsIHsgfGl8IHNlbGZbaV0gfQogICAgZW5kCiAgICBkZWYg dmFsdWVzCiAgICAgICAgZmluZF9hbGwgeyB8IGVsZW1lbnQgfCBlbGVtZW50 IH0KICAgIGVuZAplbmQKCiMgbWFrZSB0aGluZ3MgZnVsbHkgY29tcGFyYWJs ZSB0byBSYW5nZXMKIyBhbHNvICogbWFrZXMgYSBTeW50YXgKY2xhc3MgUmFu Z2UKICAgIGluY2x1ZGUgQ29tcGFyYWJsZQogICAgZGVmIDw9PihvdGhlcikK ICAgICAgICBpZiAob3RoZXI8c2VsZi5iZWdpbikKICAgICAgICAgICAgKzEK ICAgICAgICBlbHNpZiAoaWYgZXhjbHVkZV9lbmQ/IHRoZW4gb3RoZXI+PXNl bGYuZW5kIGVsc2Ugb3RoZXI+c2VsZi5lbmQgZW5kKQogICAgICAgICAgICAt MQogICAgICAgIGVsc2UKICAgICAgICAgICAgMAogICAgICAgIGVuZAogICAg ZW5kCiAgICBhbGlhcyBfb2xkX2VxdWFsID09CiAgICBkZWYgPT0ob3RoZXIp CiAgICAgICAgaWYgKG90aGVyLmtpbmRfb2Y/UmFuZ2UpCiAgICAgICAgICAg ICMgdW5kb2N1bWVudGVkIHByZXZpb3VzIGZ1bmN0aW9uYWxpdHkKICAgICAg ICAgICAgX29sZF9lcXVhbChvdGhlcikKICAgICAgICBlbHNlCiAgICAgICAg ICAgIChzZWxmPD0+b3RoZXIpPT0wCiAgICAgICAgZW5kCiAgICBlbmQKICAg IGRlZiAqKG90aGVyKQogICAgICAgIFN5bnRheDo6QXRvbS5uZXcoc2VsZiwx KSpvdGhlcgogICAgZW5kCmVuZAoKCgoK --0-371748238-1113456806=:21044--