{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/56383","repository_url":"https://api.github.com/repos/rust-lang/rust","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/56383/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/56383/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/56383/events","html_url":"https://github.com/rust-lang/rust/issues/56383","id":386287230,"node_id":"MDU6SXNzdWUzODYyODcyMzA=","number":56383,"title":"Get rid of global `AllocId` tables","user":{"login":"oli-obk","id":332036,"node_id":"MDQ6VXNlcjMzMjAzNg==","avatar_url":"https://avatars2.githubusercontent.com/u/332036?v=4","gravatar_id":"","url":"https://api.github.com/users/oli-obk","html_url":"https://github.com/oli-obk","followers_url":"https://api.github.com/users/oli-obk/followers","following_url":"https://api.github.com/users/oli-obk/following{/other_user}","gists_url":"https://api.github.com/users/oli-obk/gists{/gist_id}","starred_url":"https://api.github.com/users/oli-obk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/oli-obk/subscriptions","organizations_url":"https://api.github.com/users/oli-obk/orgs","repos_url":"https://api.github.com/users/oli-obk/repos","events_url":"https://api.github.com/users/oli-obk/events{/privacy}","received_events_url":"https://api.github.com/users/oli-obk/received_events","type":"User","site_admin":false},"labels":[{"id":900795185,"node_id":"MDU6TGFiZWw5MDA3OTUxODU=","url":"https://api.github.com/repos/rust-lang/rust/labels/A-const-eval","name":"A-const-eval","color":"f7e101","default":false},{"id":891133401,"node_id":"MDU6TGFiZWw4OTExMzM0MDE=","url":"https://api.github.com/repos/rust-lang/rust/labels/A-parallel-queries","name":"A-parallel-queries","color":"f7e101","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-11-30T17:48:23Z","updated_at":"2018-12-02T14:43:28Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"Right now we have a big global table of all allocations that the current rustc execution has need of. This doesn't fit the query system, has loads of complicated code for loading from metadata and generally complicates const eval.\r\n\r\nI believe it is a goal to ensure that the `const_eval` query result needs no further queries to inspect the `Allocation`s returned. For this, we'd need to return the entire set of `Allocation`s from the query and have some sort of local allocation ids for relocations, or just have relocations refer to `Allocation`s directly.\r\n\r\nThe direct refering to `Allocation`s is problematic if we ever allow heap allocations and thus graphs or other cyclic datastructures in constants, because then we'd have cyclic references.\r\n\r\nLocal ids are problematic, because we either have to duplicate all `Allocation`s we get from other constants, or we have to figure out a scheme to use the same `Allocation` \r\n\r\n![grafik](https://user-images.githubusercontent.com/332036/49300168-cc677d80-f4c1-11e8-9ab2-68d75d90cae3.png)\r\n<details>\r\n<summary>Click here for graphviz code of this graph</summary>\r\ndigraph G {\r\n    constA -> AllocationA -> AllocationB\r\n    AllocationA -> AllocationC\r\n    AllocationA -> AllocationY\r\n    constX -> AllocationX -> AllocationY\r\n    \r\n    constA [label=\"const A: &[&u32] = &[&5, &6, X];\r\nallocations: [A, B, C, Y]\"]\r\n    constX [label=\"const X: &u32 = &99;\r\nallocations: [X, Y]\"]\r\n    \r\n    AllocationX [label = \"X\r\n[1]\"]\r\n    AllocationY [label = \"Y\r\n[]\"]\r\n    AllocationA [label = \"A\r\n[1, 2, 3]\"]\r\n    AllocationB [label = \"B\r\n[]\"]\r\n    AllocationC [label = \"C\r\n[]\"]\r\n}\r\n</details>\r\n\r\nWe can probably find a solution for the above graph, but the one below is problematic. We'd need to duplicate the entire allocation. The allocation might be a huge constant though.\r\n\r\n![grafik](https://user-images.githubusercontent.com/332036/49301490-01c19a80-f4c5-11e8-8ee9-13272f6693aa.png)\r\n<details>\r\n<summary>Click here for graphviz code of this graph</summary>\r\ndigraph G {\r\n    node [shape=box, nojustify=true]\r\n    constA -> AllocationA -> AllocationB\r\n    AllocationA -> AllocationC\r\n    AllocationA -> AllocationY\r\n    AllocationC -> AllocationD\r\n    AllocationB -> AllocationE\r\n    AllocationY -> AllocationZ\r\n    constX -> AllocationX -> AllocationY\r\n    \r\n    constA [label=\"const A: &[&&u32] = &[&&5, &&6, X];\r\nallocations: [A, B, C, D, E, Y, Z]\"]\r\n    constX [label=\"const X: &u32 = &99;\r\nallocations: [X, Y, Z]\"]\r\n    \r\n    AllocationX [label = \"X\\n[1]\"]\r\n    AllocationY [label = \"Y\\n[?? 6 or 2 ??]\"]\r\n    AllocationA [label = \"A\\n[1, 2, 5]\"]\r\n    AllocationB [label = \"B\\n[4]\"]\r\n    AllocationC [label = \"C\\n[3]\"]\r\n    AllocationZ [label = \"Z\\n[]\"]\r\n    AllocationE [label = \"E\\n[]\"]\r\n    AllocationD [label = \"D\\n[]\"]\r\n}\r\n</details>\r\n\r\nOf course we can move to fully refering to the other constant in order to get a its memory. I initially thought that such a scheme would require all our const eval pointers to contain a `DefId`, `Substs`, `ParamEnv` and an optional promoted index (which are the four components in a `GlobalId` required for fully identifying a constant, statics just need a `DefId` as long as they stay nongeneric). That's a serious increase in size (from `u64` currently).\r\n\r\n![grafik](https://user-images.githubusercontent.com/332036/49305184-d93e9e00-f4ce-11e8-81e1-b6a919e72dd2.png)\r\n<details>\r\n<summary>Click here for graphviz code of this graph</summary>\r\ndigraph G {\r\n    node [shape=box, nojustify=true]\r\n    constA -> AllocationA -> AllocationB\r\n    AllocationA -> AllocationC\r\n    AllocationA -> AllocationY\r\n    AllocationC -> AllocationD\r\n    AllocationB -> AllocationE\r\n    AllocationY -> AllocationZ\r\n    constX -> AllocationX -> AllocationY\r\n    \r\n    constA [label=\"const A: &[&&u32] = &[&&5, &&6, X];\r\nallocations: [A, B, C, D, E]\"]\r\n    constX [label=\"const X: &u32 = &99;\r\nallocations: [X, Y, Z]\"]\r\n    \r\n    AllocationX [label = \"X\\n[1]\"]\r\n    AllocationY [label = \"Y\\n[2]\"]\r\n    AllocationA [label = \"A\\n[1, 2, X[1]]\"]\r\n    AllocationB [label = \"B\\n[4]\"]\r\n    AllocationC [label = \"C\\n[3]\"]\r\n    AllocationZ [label = \"Z\\n[]\"]\r\n    AllocationE [label = \"E\\n[]\"]\r\n    AllocationD [label = \"D\\n[]\"]\r\n}\r\n</details>\r\n\r\nBut we can store these `GlobalId`s in the `ty::Const` value and just refer to them via an index:\r\n\r\n![grafik](https://user-images.githubusercontent.com/332036/49305680-325b0180-f4d0-11e8-95d9-9c6613fc3a2a.png)\r\n<details>\r\n<summary>Click here for graphviz code of this graph</summary>\r\ndigraph G {\r\n    node [shape=box, nojustify=true]\r\n    constA -> AllocationA -> AllocationB\r\n    AllocationA -> AllocationC\r\n    AllocationA -> AllocationY\r\n    AllocationC -> AllocationD\r\n    AllocationB -> AllocationE\r\n    AllocationY -> AllocationZ\r\n    constX -> AllocationX -> AllocationY\r\n    \r\n    constA [label=\"const A: &[&&u32] = &[&&5, &&6, X];\r\nallocations: [A, B, C, D, E, X[1]]\"]\r\n    constX [label=\"const X: &u32 = &99;\r\nallocations: [X, Y, Z]\"]\r\n    \r\n    AllocationX [label = \"X\\n[1]\"]\r\n    AllocationY [label = \"Y\\n[2]\"]\r\n    AllocationA [label = \"A\\n[1, 2, 5]\"]\r\n    AllocationB [label = \"B\\n[4]\"]\r\n    AllocationC [label = \"C\\n[3]\"]\r\n    AllocationZ [label = \"Z\\n[]\"]\r\n    AllocationE [label = \"E\\n[]\"]\r\n    AllocationD [label = \"D\\n[]\"]\r\n}\r\n</details>\r\n\r\nSo... Anyone wants to poke holes into the last scheme? @Zoxc @eddyb @RalfJung "},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/443512814","html_url":"https://github.com/rust-lang/rust/issues/56383#issuecomment-443512814","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/56383","id":443512814,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MzUxMjgxNA==","user":{"login":"eddyb","id":77424,"node_id":"MDQ6VXNlcjc3NDI0","avatar_url":"https://avatars2.githubusercontent.com/u/77424?v=4","gravatar_id":"","url":"https://api.github.com/users/eddyb","html_url":"https://github.com/eddyb","followers_url":"https://api.github.com/users/eddyb/followers","following_url":"https://api.github.com/users/eddyb/following{/other_user}","gists_url":"https://api.github.com/users/eddyb/gists{/gist_id}","starred_url":"https://api.github.com/users/eddyb/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/eddyb/subscriptions","organizations_url":"https://api.github.com/users/eddyb/orgs","repos_url":"https://api.github.com/users/eddyb/repos","events_url":"https://api.github.com/users/eddyb/events{/privacy}","received_events_url":"https://api.github.com/users/eddyb/received_events","type":"User","site_admin":false},"created_at":"2018-12-02T14:43:28Z","updated_at":"2018-12-02T14:43:28Z","author_association":"MEMBER","body":"I'm guessing interning `Allocation`s just before `const_eval` returns isn't an option?\r\n\r\nAs for encoding things using indices, it sounds a lot like some sort of \"de Bruijn\" scheme and/or substitution, cc @nikomatsakis  "}}
{"actor":{"display_login":"eddyb"}}