{"action":"created","issue":{"url":"https://api.github.com/repos/binast/binjs-ref/issues/115","repository_url":"https://api.github.com/repos/binast/binjs-ref","labels_url":"https://api.github.com/repos/binast/binjs-ref/issues/115/labels{/name}","comments_url":"https://api.github.com/repos/binast/binjs-ref/issues/115/comments","events_url":"https://api.github.com/repos/binast/binjs-ref/issues/115/events","html_url":"https://github.com/binast/binjs-ref/issues/115","id":319086747,"number":115,"title":"Pre-defined grammar table with file-local remap in multipart .binjs file ","user":{"login":"arai-a","id":6299746,"avatar_url":"https://avatars1.githubusercontent.com/u/6299746?v=4","gravatar_id":"","url":"https://api.github.com/users/arai-a","html_url":"https://github.com/arai-a","followers_url":"https://api.github.com/users/arai-a/followers","following_url":"https://api.github.com/users/arai-a/following{/other_user}","gists_url":"https://api.github.com/users/arai-a/gists{/gist_id}","starred_url":"https://api.github.com/users/arai-a/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/arai-a/subscriptions","organizations_url":"https://api.github.com/users/arai-a/orgs","repos_url":"https://api.github.com/users/arai-a/repos","events_url":"https://api.github.com/users/arai-a/events{/privacy}","received_events_url":"https://api.github.com/users/arai-a/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-05-01T01:09:39Z","updated_at":"2018-05-11T06:03:51Z","closed_at":null,"author_association":"COLLABORATOR","body":"# Background\r\n\r\nThe multipart format for `.binjs` file contains `[GRAMMAR]` section, that defines the table for index for each interface (or grammar name?) used in the file, like, 0 => CallExpression.\r\n\r\n# Problem\r\n\r\nCurrently there are 106 interfaces in `BinSource.webidl_` file, and enumerating all of them takes ~2kB for each file.\r\n\r\n# Solution\r\n\r\nPre-define the table, and store it inside the engine.\r\n\r\n## Pros\r\n\r\n1. The `.binjs` file size can be reduced by up to 2kB, before compression\r\n2. The time taken by parsing `[GRAMMAR]` section can be reduced\r\n\r\n## Cons\r\n\r\n1. If the number of interfaces becomes more than 127 in the future, index for some interface will take 2bytes, and `[TREE]` may take more spaces compared to the current format\r\n2. If unknown grammar is used in the file, the engine cannot show the detail about the error (like, which syntax is not supported)\r\n\r\n# Optimization for solving the Cons 1\r\n\r\nEmbed an information for remapping the index, in `[GRAMMAR]` section.\r\n\r\n## Example\r\n\r\nConsider that the predefined table looks like the following (just an example, the actual table should use more efficient order):\r\n\r\n| Index | Interface |\r\n| ----- | --------- |\r\n| 0     | _Null |\r\n| 1     | VariableDeclaration |\r\n| 2     | CallExpression |\r\n| 3     | WhileStatement |\r\n| 4     | SwitchCase |\r\n| ...   | ... |\r\n| 50    | ExpressionStatement |\r\n| ...   | ... |\r\n| 180   | IdentifierExpression |\r\n| ...   | ... |\r\n| 200   | LiteralNumericExpression |\r\n| ...   | ... |\r\n| 260   | Script |\r\n| ...   | ... |\r\n\r\nThe `[TREE]` for `print(10);` will look like the following byte stream:\r\n\r\n```\r\n28                       # treeByteLen = 21\r\nF5 02                    # = 260 (Script)\r\n00                       # Script.OptionalAssertedVarScope = _Null\r\n00                       # Script.ListOfDirective.items = 0\r\n02                       # Script.parseListOfStatement.items = 1\r\n64                       # = 50 (ExpressionStatement)\r\n04                       # = 2 (CallExpression)\r\n69 02                    # = 180 (IdentifierExpression)\r\n00                       # IdentifierExpression.name = \"print\"\r\n02                       # Arguments.items = 1\r\n91 02                    # = 200 (LiteralNumericExpression)\r\n00 00 00 00 00 00 24 40  # LiteralNumericExpression.value = 10\r\n```\r\n\r\nThere, `IdentifierExpression`, `LiteralNumericExpression`, and `Script` are taking 2 bytes, while most interfaces with 1 bytes are not used there.\r\n\r\nIf we remap the table like the following:\r\n\r\n| Index | Interface |\r\n| ----- | --------- |\r\n| 0     | _Null |\r\n| 1     | **IdentifierExpression** |\r\n| 2     | CallExpression |\r\n| 3     | **LiteralNumericExpression** |\r\n| 4     | **Script**                    |\r\n| ...   | ... |\r\n| 50    | ExpressionStatement |\r\n| ...   | ... |\r\n| 180   | IdentifierExpression |\r\n| ...   | ... |\r\n| 200   | LiteralNumericExpression |\r\n| ...   | ... |\r\n| 260   | Script |\r\n| ...   | ... |\r\n\r\nThe `[TREE]` for `print(10);` will become the following byte stream:\r\n\r\n```\r\n24                       # treeByteLen = 18\r\n08                       # = 4 (Script)\r\n00                       # Script.OptionalAssertedVarScope = _Null\r\n00                       # Script.ListOfDirective.items = 0\r\n02                       # Script.parseListOfStatement.items = 1\r\n64                       # = 50 (ExpressionStatement)\r\n04                       # = 2 (CallExpression)\r\n02                       # = 1 (IdentifierExpression)\r\n00                       # IdentifierExpression.name = \"print\"\r\n02                       # Arguments.items = 1\r\n06                       # = 3 (LiteralNumericExpression)\r\n00 00 00 00 00 00 24 40  # LiteralNumericExpression.value = 10\r\n```\r\n\r\nThe remap can be encoded like the following byte stream:\r\n\r\n```\r\n69 02  # from: 180 (IdentifierExpression)\r\n02     # to:   1\r\n91 02  # from: 200 (LiteralNumericExpression)\r\n06     # to:   3\r\nF5 02  # from: 260 (Script)\r\n08     # to:   4\r\n```\r\n\r\nIn this small example, the actual file size increases tho, in the large code, the size taken by the remap information will be negligible, compared to the `[TREE]` data reduction.\r\n\r\nEncoder can choose whether to remap or not, depending on the file content.\r\nThey can remap interfaces with 2bytes index only when the interface is used many times in the file content.\r\n\r\n# Handling grammar evolution/extensions\r\n\r\nFor the base ES grammar, the grammar table is supposed to extend over time, keeping the index for pre-existing interfaces same.\r\n\r\nFor proposals, including the ECMAScript spec proposals and BinAST-specific optimization etc, there can be multiple proposal at once, so the table can temporarily branch.\r\n\r\nThis can be solved by the namespace (thanks to @RReverser), and merging table.\r\n\r\n## Namespace\r\n\r\nEach proposal should have their own namespace (maybe URL-like thing), and namespace-local table (index => interface).\r\n\r\nBy keeping the table's pre-existing entry's index same, we don't have to add version number for the namespace.\r\n\r\n## Merging table\r\n\r\nSupposing the pre-existing index keeps same over time, the merging can be done just by putting the table entries into file-local index.\r\n\r\n### Example\r\n\r\nSuppose there are 3 tables:\r\n1. the base ES grammar, which has 106 entries at the time of generating the `.binjs` file\r\n2. a proposal for adding Class fields grammar, which has 2 entries, and its namespace is \"tc39/proposal-class-fields\"\r\n3. a proposal for adding optimized LiteralNumericExpression, which has 4 entries, and its namespace is \"binjs/optimized-numeric\"\r\n\r\nThe file can merge the table by specifying the following information:\r\n* the namespace: \"tc39/proposal-class-fields\" or \"binjs/optimized-numeric\"\r\n* the start index for the namespace: 106 and 108\r\n\r\nSo that the table is merged like the following:\r\n\r\n| Index | Interface |\r\n| ----- | --------- |\r\n| 0     | _Null |\r\n| 1     | ArrayAssignmentTarget |\r\n| 2     | ArrayBinding |\r\n| 3     | ArrayExpression |\r\n| ... | ... |\r\n| 104 | YieldExpression |\r\n| 105 | YieldStarExpression |\r\n| **106** | **ClassPublicField** (from tc39/proposal-class-fields\")  |\r\n| **107** | **ClassPrivateField** (from tc39/proposal-class-fields\") |\r\n| **108** | **LiteralInt8Expression** (from binjs/optimized-numeric) |\r\n| **109** | **LiteralInt16Expression** (from binjs/optimized-numeric) |\r\n| **110** | **LiteralInt32Expression** (from binjs/optimized-numeric) |\r\n| **111** | **LiteralFloatExpression** (from binjs/optimized-numeric) |\r\n\r\nThe base ES grammar and both proposals may evolve over time, after the file is generated.\r\nBut as long as the index for pre-existing entries keep same, and the merge is done from the smaller index, the merged table keeps same for the range used by the file.\r\n\r\nThe file-local remap can be done after the merge, in order to use smaller indices.\r\n\r\n## Solution for Cons 2\r\n\r\nBy providing the definition for each namespace in the external resource, possibly via the URL, the engine can retrieve the definition and can give users the detail about the error.\r\n\r\nThe engine can include the cache for base ES grammar, and as long as the index used by the file doesn't exceed the maximum index in the known table, it can use the cached table.\r\nOnce the index used in the file goes beyond the known maximum index, or the file contains unknown namespace, the engine can retrieve the definition if necessary.\r\n(maybe only when showing the error)\r\n"},"comment":{"url":"https://api.github.com/repos/binast/binjs-ref/issues/comments/388268906","html_url":"https://github.com/binast/binjs-ref/issues/115#issuecomment-388268906","issue_url":"https://api.github.com/repos/binast/binjs-ref/issues/115","id":388268906,"user":{"login":"Yoric","id":10190,"avatar_url":"https://avatars1.githubusercontent.com/u/10190?v=4","gravatar_id":"","url":"https://api.github.com/users/Yoric","html_url":"https://github.com/Yoric","followers_url":"https://api.github.com/users/Yoric/followers","following_url":"https://api.github.com/users/Yoric/following{/other_user}","gists_url":"https://api.github.com/users/Yoric/gists{/gist_id}","starred_url":"https://api.github.com/users/Yoric/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Yoric/subscriptions","organizations_url":"https://api.github.com/users/Yoric/orgs","repos_url":"https://api.github.com/users/Yoric/repos","events_url":"https://api.github.com/users/Yoric/events{/privacy}","received_events_url":"https://api.github.com/users/Yoric/received_events","type":"User","site_admin":false},"created_at":"2018-05-11T06:03:51Z","updated_at":"2018-05-11T06:03:51Z","author_association":"COLLABORATOR","body":"For the moment, I'm concentrating on what I hope will be larger gains: #126."}}
{"actor":{"display_login":"Yoric"}}