Title: Half a variadic tuple rest sandwich matching algorithm missing · Issue #49105 · microsoft/TypeScript · GitHub
Open Graph Title: Half a variadic tuple rest sandwich matching algorithm missing · Issue #49105 · microsoft/TypeScript
X Title: Half a variadic tuple rest sandwich matching algorithm missing · Issue #49105 · microsoft/TypeScript
Description: Half a variadic tuple rest sandwich missing Bug Report 🔎 Search Terms variadic tuple assignment matching algorithm Background When a non-generic variadic tuple of arbitrary depth is declared, it is transformed into one of two possible fi...
Open Graph Description: Half a variadic tuple rest sandwich missing Bug Report 🔎 Search Terms variadic tuple assignment matching algorithm Background When a non-generic variadic tuple of arbitrary depth is declared, it is...
X Description: Half a variadic tuple rest sandwich missing Bug Report 🔎 Search Terms variadic tuple assignment matching algorithm Background When a non-generic variadic tuple of arbitrary depth is declared, it is...
Opengraph URL: https://github.com/microsoft/TypeScript/issues/49105
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Half a variadic tuple rest sandwich matching algorithm missing","articleBody":"Half a variadic tuple rest sandwich missing\r\n\r\n# Bug Report\r\n### 🔎 Search Terms\r\n\r\nvariadic tuple assignment matching algorithm\r\n\r\n#### Background\r\n\r\nWhen a non-generic variadic tuple of arbitrary depth is declared, \r\nit is transformed into one of two possible final flat canonical forms,\r\nas described by this comment\r\n```\r\n// We have optional, rest, or variadic elements that may need normalizing. Normalization ensures that all variadic\r\n// elements are generic and that the tuple type has one of the following layouts, disregarding variadic elements:\r\n// (1) Zero or more required elements, followed by zero or more optional elements, followed by zero or one rest element.\r\n// (2) Zero or more required elements, followed by a rest element, followed by zero or more required elements.\r\n// In either layout, zero or more generic variadic elements may be present at any location.\r\n```\r\nfound in `checker.ts`, `function createNormalizedTupleType`.\r\n\r\n#### Bug \r\n\r\nHowever, the current unidirectional matching algorithm in `checkArrayLiteral` does not work correctly with the output from \r\n`createNormalizedTupleType`. It incorrectly gives errors. (Incorrect meaning, it returns errors for lhs values that could pass if a full combinatorial search were used.\r\n\r\nThat's because `checkArrayLiteral` performs a unidirection (left to right) search only, whereas the output from `createNormalizedTupleType` requires a bidirectional search. \r\n\r\nOne solution would be be to change the output of `createNormalizedTupleType` so that it all elements to the right off the first rest element were rolled into a single rest. Then the unidirectional search could be used with returning false errors.\r\n\r\nHowever, a bidirectional search takes the same O(1) time as the unidirectional search, yet \r\nyet produces fewer false postives (false passes) than the unidirectional search. Therefore the bidirectional search is prefereable.\r\n\r\nThe bidirectional matching algorithm intended by the output of `createNormalizedTupleType` is \r\n\r\n- match values from the front until the rest element is reached, \r\n- match values from the back until the rest element is reached,\r\n- match the remaining values to the rest element.\r\n\r\n\r\n### 🕗 Version & Regression Information\r\n\r\nThe example wrong assignment results for variadic tuples are stable in version range 4.2.3 ~ 4.8 dev.\r\n\r\n### ⏯ Playground Link\r\n\r\n[playground](https://www.typescriptlang.org/play?exactOptionalPropertyTypes=false#code/PTAEAEGcBcCcEsDG0Bco4FcCmAoEEsAPAQ2QHkAHaeAewDtiAbABVhoq1mgE8AVbjpDQAzJpFx4AVJJyhJoXgAssoAEZZhNWFjQAKMgGlgAUVhtYASlAANULqIdkWACbAMdB1ifOrdGtGJqekhQenRlUFhFENl5GmFwlWJISHgAczoAWyw6aBDibVAANyZ4Z1BNWGLOVODQABYAOgAmRoBmUAA-BsaADlBnLCLG2OAcHABvWVAZ-H4OBWbQAEkAZVAAOTJeUGJIrBhQSGI6ZwB3JEUKrUzA0ABaXcYz4m4Qv1BERRO0lXg6faQDCMaBqLDQM5YHJgypJU67YTQTjTGY8Ba8ACMoAAvKAANqEFB0DCZdSwAA03AA-ChVDQaIwsCcALoAbhR6AEKl4S1xeMaAsx5NAACIACQitmzMAAcQAqssjooaGcQmjubz8cTSZxhXSGUyAQAfUDuQbCf4uYXiyWfE70JBMTkLLGVW6g3QfbQwCzjGYzRDBUHQZrEFA8nH4jHWiVS-ATGFaHSgUzmOyebwWYXERGcNCprTpwiOJE+UAAXw5gbohxDqnDmrx0fQsGwMclrNA8cT2jQhiLJZcWYRSNgfYMA68paslcrkw5cy5CgxSzWu0BoOOpwuX2usHdD3C8BCRGImQojKVKpC3uBeXCd3g57YJVUjG4A3gwmEnDBEKhALqLCuzwjmo4jP6zoqAAMskoK4ja7KQeqy5YnyhIigAeiK5ICo03C0vSjInHizJshyKGYhimSRniABeNIwAgdBpORyFLpijZ4VRwrcRi1HkjacZgJRK60VhOGgHhuhMf8aSgCa+rEcapqnBolo+KR7bMnafh0I6jBQaASxuncujepuJznJcvoLtIoAcvIywAtAEQeIQwZnDQuwpOkWQ5KCp7noyQiOf6QFJmgrkqGkjAYNQfgYDeByBYy2S5KAAAGnFNsymWgGk2guPA76gEy97RZE0RZWKmXChQ2hFAFclZTlzR5RUbA0YGZhTqV7pfC1UQhJltWNA5kHyDMYF5hU8CwIc2UrniAAMHUDcoN7VRJwoWWVaUBa1y0YutgSDSxoDHgMGg-tozjCktzR4u1mUbQciSgIwcGihKwphZBVlzQwjD9Wdm0fXtWAHRlj25ZlEH+pIYyQdWtYrmGnHidh2mdt2EW9imZiFro7gZtO2a5mOoD9vYxZTkOFYTf6qPBiu9aY3yO0tm2P0dl2YAJvjKgoAWVQk+5g4+BTo7jpOmYVn6-r4M5H3uZ53nJKkGTpYFJDBQcwqVULqlky4ZVEwtuyFA1QwBWbqgfg4jBIPAPB2jAQ3bRK6DeZVzujk6KGu-sTClVd2QnMG3nqOSC5gGciiXJd7z+J8NDnoE8BvioFyuRDKX7VgOtHU9J3wzMShXVdABWSVR5dIN17AgQqMqZwfe4ZTzV4rv0E60E+6AABKoAbS1V1ebAADWclxyB5SICcRzp+CT7vb8wYRAgaSKKCJyQJCsAIwGQboCuiDhmJnPY7zPmgLBMDCaAgsaJF1MTrTkvDjNVM06bZaVhRqfaAK5nCX0bFzTAWB2x3wftAJ+L9YSy0-vTKWI5Zp-zpvLWcOAgA)\r\n\r\n### 💻 Code\r\n\r\n```ts\r\n// @strict: true\r\n// @exactOptionalPropertyTypes: false\r\n\r\n/**\r\n * The before: (OK/Error) X (expected/unexpected) notations on the rhs \r\n * of the assignments are valid for versions 4.2.3 ~ 4.8 dev.\r\n */\r\n\r\n{\r\n // Type T2 IS NOT a rest sandwich format - always no change in result between before and after\r\n type T1 = [x:number,y?:boolean];\r\n type T2 = [...T1, \"$\"]; // GUI shows type T2 = [number, boolean | undefined, \"$\"] canonical type 1 format (no rest)\r\n\r\n const t2a:T2 = [1, \"$\"]; // { before: Error (expected), after: Error (expected) } \r\n const t2b:T2 = [1, true, \"$\"]; // { before: OK (expected), after: OK (expected) }\r\n}\r\n\r\n{\r\n // Type T12 IS a rest sandwich format - this example shows results that improvably differ between before and after.\r\n type Last = \"$\";\r\n type T11 = [x:\"^\",...y:boolean[]];\r\n type T11m = [z?:string];\r\n type T12 = [...T11, ...T11m,\"$\"]; // type T12 = [\"^\", ...(string | boolean | undefined)[], \"$\"] canonical type 2 format (rest sandwich)\r\n\r\n /** \r\n * In the next two assignment examples:\r\n * before: the glutinous rest element `T12[1]` greedily eats the rhs `$`, preventing `T12[2]` from correctly matching rhs `$`. \r\n * after: first `T12[0]` matches rhs \"^\", rest element `T12[1]` matching is deffered, `T12[2]`matches the last \"$\", \r\n * and finally matches the rest element `T12[1]`.\r\n */\r\n const t12a:T12 = [\"^\", \"$\"]; // { before: Error (unexpected), after: OK (expected) } // BUG\r\n const t12b:T12 = [\"^\", true, \"$\"]; // { before :Error (unexpected), after: OK (expected) } // BUG\r\n\r\n // In the next two assignment examples, the before unexpected errors are prevented by explicity casting rhs \"$\" to the literal type it really is meant to be,\r\n // which is not compatible with the rest element `T12[1]`. This is just to illustrate how the unidirecitonal L to R matching is working\r\n // and can sometimes get the right answer.\r\n const t12c:T12 = [\"^\", \"$\" as Last]; // { before: OK (expected), after: OK (expected) }\r\n const t12d:T12 = [\"^\", true, \"$\" as Last]; // { before: OK (expected), after: OK (expected) }\r\n}\r\n```\r\n\r\n### 🙁 Actual behavior\r\n\r\nMatching from left to right (Alg1).\r\nInvalid results found.\r\n\r\n### 🙂 Expected behavior\r\n\r\nUsing the bidirectional, rest-centered search described above no invalid results would be found.\r\n\r\n### Deep analysis\r\n\r\nIn order to properly analyze the the specs, I felt I had to write an implementation of the bidirectional search\r\nand run it on the baseline tests. That's work is in the \"pull draft\" #49106.\r\nOf course I assume this \"pull draft\" will not be used, but the analysis result are still valid, and potentially useful. \r\n \r\nTo summarize the analysis, the way the code is currently written (4.7) there is assumption that array context types \r\ndon't necessarily need to expose a length for use in matching. However that won't necessarily work when\r\ntrying to match with a bidirectional search. Might be able to get away with negative indices \r\n(distance from the end) and still avoid length. But stretching a rest element to infinite length won't work when a bidirectional search is required.\r\n","author":{"url":"https://github.com/craigphicks","@type":"Person","name":"craigphicks"},"datePublished":"2022-05-14T08:04:48Z","url":"https://github.com/microsoft/TypeScript/issues/49105"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:10df56f1-8420-a700-37a9-902d2b00602f |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 9378:27E5CD:2C1B8CE:386CFA5:6B01A7CA |
| html-safe-nonce | 51a0d62127d057945918189148a390fa3d6048694df70779d79b99a6ef22fb89 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5Mzc4OjI3RTVDRDoyQzFCOENFOjM4NkNGQTU6NkIwMUE3Q0EiLCJ2aXNpdG9yX2lkIjoiNTEzNTkyMDc4NjI1MDUwODIzNCIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9 |
| visitor-hmac | 9c03238b236de82d021ee51616893d226ff59b3d3f8bcd3b96d1a934f3c547e2 |
| hovercard-subject-tag | issue:1235909979 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/microsoft/TypeScript/49105/issue_layout |
| twitter:image | https://opengraph.githubassets.com/0da74722ed7daf681ee1246df4f6a9694210263d3596ca09d7b564f427b73e4c/microsoft/TypeScript/issues/49105 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/0da74722ed7daf681ee1246df4f6a9694210263d3596ca09d7b564f427b73e4c/microsoft/TypeScript/issues/49105 |
| og:image:alt | Half a variadic tuple rest sandwich missing Bug Report 🔎 Search Terms variadic tuple assignment matching algorithm Background When a non-generic variadic tuple of arbitrary depth is declared, it is... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | craigphicks |
| hostname | github.com |
| expected-hostname | github.com |
| None | cc5dfdd32f62ebd3223cab3af3aa2b268d3605218237326a48a99d1efd89495c |
| turbo-cache-control | no-preview |
| go-import | github.com/microsoft/TypeScript git https://github.com/microsoft/TypeScript.git |
| octolytics-dimension-user_id | 6154722 |
| octolytics-dimension-user_login | microsoft |
| octolytics-dimension-repository_id | 20929025 |
| octolytics-dimension-repository_nwo | microsoft/TypeScript |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 20929025 |
| octolytics-dimension-repository_network_root_nwo | microsoft/TypeScript |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 8c77c9e8439031ad54c75a250694842892f693e1 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width