Bug 15831 – IFTI voldemort type exploding bloat

The current name mangling rules for template expansion lead to excessive bloat when voldemort types are returned and used in subsequent chained calls. This pattern is used in some places in Phobos for instance to allow wrapped ranges. An example is std.range.chain. If this pattern is used recursively, the resulting template mangling expands at an exponential rate, because the template parameter is used multiple times in the expansion (once for the type name for the template, and once for the type name of the parameter). Because the return type depends on the function name mangling, the cycle continues as you expand the chain. A simple example: (Please read through the whole bug report, as I have comments in between a lot of output) struct S(T) { void foo(){ throw new Exception("1");} } auto s(T)(T t) { version(bad) { struct Result { void foo(){ throw new Exception("2");} } return Result(); } else return S!T(); } void main(string[] args) { auto x = 1.s.s.s.s.s; x.foo; } If I compile this without -version=bad, I get this: Stevens-MacBook-Pro:testd steves$ time dmd testexpansion.d real 0m0.058s user 0m0.040s sys 0m0.014s Stevens-MacBook-Pro:testd steves$ ls -l testexpansion* -rwxr-xr-x+ 1 steves staff 409948 Mar 25 11:59 testexpansion -rw-r--r--+ 1 steves staff 324 Mar 25 11:59 testexpansion.d -rw-r--r--+ 1 steves staff 7104 Mar 25 11:59 testexpansion.o Stevens-MacBook-Pro:testd steves$ ./testexpansion [email protected](3): 1 ---------------- 4 testexpansion 0x00000001050edc14 pure @safe void testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(int).S).S).S).S).S.foo() + 144 5 testexpansion 0x00000001050ed837 _Dmain + 119 6 ... # etc. Now, let's compile with the -bad version: Stevens-MacBook-Pro:testd steves$ time dmd -version=bad testexpansion.d real 0m0.058s user 0m0.041s sys 0m0.014s Stevens-MacBook-Pro:testd steves$ ls -l testexpansion* -rwxr-xr-x+ 1 steves staff 429412 Mar 25 12:00 testexpansion -rw-r--r--+ 1 steves staff 324 Mar 25 11:59 testexpansion.d -rw-r--r--+ 1 steves staff 15312 Mar 25 12:00 testexpansion.o Stevens-MacBook-Pro:testd steves$ ./testexpansion [email protected](12): 2 ---------------- 4 testexpansion 0x000000010f639c0c pure @safe void testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result.foo() + 144 5 testexpansion 0x000000010f639807 _Dmain + 119 6 ... # etc. Note the extreme increase in object size. Also note the much larger symbol name when the exception is thrown. Let's expand the number of s calls to 10: auto x = 1.s.s.s.s.s.s.s.s.s.s; New results: Stevens-MacBook-Pro:testd steves$ time dmd testexpansion.d real 0m0.074s user 0m0.043s sys 0m0.018s Stevens-MacBook-Pro:testd steves$ ls -l testexpansion* -rwxr-xr-x+ 1 steves staff 431716 Mar 25 14:01 testexpansion -rw-r--r--+ 1 steves staff 334 Mar 25 14:01 testexpansion.d -rw-r--r--+ 1 steves staff 16528 Mar 25 14:01 testexpansion.o OK, so the size of the object doubled for doubling the number of calls/types. Not unexpected. Stevens-MacBook-Pro:testd steves$ ./testexpansion [email protected](3): 1 ---------------- 4 testexpansion 0x0000000104816bec pure @safe void testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(int).S).S).S).S).S).S).S).S).S).S.foo() + 144 5 testexpansion 0x00000001048164c6 _Dmain + 214 6 ... # etc. A reasonable expanding of the symbol name. Let's try the bad version: Stevens-MacBook-Pro:testd steves$ time dmd -version=bad testexpansion.d real 0m0.164s user 0m0.145s sys 0m0.016s Comparing to original compilation time of testexpansion with bad version (0.058s), this is a significant slowdown. My tests show me that the major slowdown is calling the linker. Stevens-MacBook-Pro:testd steves$ ls -l testexpansion* -rwxr-xr-x+ 1 steves staff 1308740 Mar 25 14:01 testexpansion -rw-r--r--+ 1 steves staff 334 Mar 25 14:01 testexpansion.d -rw-r--r--+ 1 steves staff 382168 Mar 25 14:01 testexpansion.o Here the object has drastically blown up from 15k to 382k. I'm timing the execution, because this is significant as well: Stevens-MacBook-Pro:testd steves$ time ./testexpansion [email protected](12): 2 ---------------- 4 testexpansion 0x0000000109b83bec pure @safe void testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(i 5 testexpansion 0x0000000109b83476 _Dmain + 214 6 ... # etc. real 0m2.801s user 0m2.790s sys 0m0.004s That's right, it takes 2.8 seconds to decide to print not quite the entire symbol name, before giving up. So this affects runtime issues as well. I tried adding 5 more calls to .s, and the object file climbed to 12MB, along with the compilation taking at least 1.5 minutes before I killed it. This is not a real-world example, but I have encountered real world examples with my iopipe library. Originally I made all the wrapping types voldemort types. Compiling a test program was at about 10MB and showed similar slowdowns when an exception was thrown. Moving the voldemort types outside the functions reduced the size to <1MB, and fixed the exception problems. I think if Phobos used more voldemort types and less external structs (there actually aren't that many voldemort ones as early range/algorithm code didn't have the luxury), I think we would have run into this sooner. We need some way to elide all the repeated type names, either via compression or substitution, or something. If we can factor out the multiplier for the symbol mangling, we can fix the problem.

As I posted on the newsgroup, I would suggest the following changes to the mangling: 1) `LName`s of length 0 (which currently cannot exist) mean to repeat the previous `LName` of the current symbol. 2) N `Number` is added as a valid `Type`, meaning "Type Back Reference". Basically, all instances of a struct/class/interface/enum type in a symbol's mangling get counted (starting from zero), and subsequent instances of that type can be referred to by N0, N1, N2, etc. Given: ``` module mod; struct Foo; Foo* func(Foo* a, Foo* b); ``` `func` currently mangles as: _D3mod4funcFPS3mod3FooPS3mod3FooZPS3mod3Foo It would instead mangle as: _D3mod4funcFPS3mod3FooPN0ZPN0 Nested template declarations would get numbered depth first as follows: S7!(S2!(S0, S1), S6!(S3, S5!(S4))) This, on its own, won't eliminate the recursive expansion bloat, but (based on manual experiments I've now done), takes foo's mangled name length almost linear with respect to the number of recursions: Recursive calls to s() before x.foo : 1 | 2 | 3 | 4 | 5 Current mangle length of foo (bytes): 39 | 90 | 192 | 397 | 807 Same, with proposed mangling changes: 38 | 64 | 90 | 116 | 148 As I said on the newsgroup, I have another idea relating to template string value mangling, but that is only tangentially related to this bug (in that both reducing mangle bloat). I'll post that separately once it is ready.

Hi Anon, I've started implementing your idea. But perhaps you already have a beginning of an implementation? If so, please contact me :) Thanks, Johan

*** Issue 16039 has been marked as a duplicate of this issue. ***

I tried to untangle the name of the 1.s.s.s.s.s case. Replacing testexpansion with E, I get E.s!(E.s!(E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .s (E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .Result) .s (E.s!(E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .s (E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .Result) .Result.foo() Each step has a mangling of "E.s!(T).s(T).Result" with T being the template argument. The length explosion comes from the type being listed twice. This is not caused by the Voldemort return type, but the eponymous template that is created by the function template.

The compressor does a good job with this: _D3foo8__T1sTiZ1sFNaNbNiNfiZS3foo8__T1sTiZ1sFiZ6Result _D3foo33__T1sTS€„8€†ŒiZáFá6Result€„NaNbNiNf€›¦€…›€¦Î€›žþ _D3foo84__T1sTS€„33€‹8€†ŒiZáFá6Result€„€›ž€‹¦NaNbNiNf€ÎÙ€†£Ø´€ÎÑþ _D3foo186__T1sTS€„Ž84€‹33€Œš€†ŒiZáFá6Result€„€›ž€¦€ÉÑ€‹®NaNbNiNf‰´¿€…«‹À‰´·þ _D3foo391__T1sTS€„Ž186€‹Ž84€‹33€Œš€†ŒiZáFá6Result€„€›ž€¦€ÉÑ€‘®‰®·€‹¶NaNbNiNf›Œ€†ÞžŒ››„þ Note how the identifier length increases: 8 => 33 => 84 => 186 => 391 but the compressed version doesn't grow nearly so fast. LZW compression is really good at removing redundancy.

For anyone who want to try a new scheme for reducing the symbol size: have a look at the test case for issue 16039 where a simple change makes the binary size explode from 18MB to over 400MB. https://issues.dlang.org/show_bug.cgi?id=16039

https://github.com/dlang/dmd/pull/5855 yields these symbols: _D13testexpansion__T1sTiZ1@FiZ6Result3fooMFNaNfZv _D13testexpansion__T1sTS0@__T1@TiZ1@FiZ6ResultZ1@F%0Z2@3fooMFNaNfZv _D13testexpansion__T1sTS0@__T1@TS0@__T1@TiZ1@FiZ6ResultZ1@F%1Z2@Z1@F%0Z2@3fooMFNaNfZv _D13testexpansion__T1sTS0@__T1@TS0@__T1@TS0@__T1@TiZ1@FiZ6ResultZ1@F%2Z2@Z1@F%1Z2@Z1@F%0Z2@3fooMFNaNfZv _D13testexpansion__T1sTS0@__T1@TS0@__T1@TS0@__T1@TS0@__T1@TiZ1@FiZ6ResultZ1@F%3Z 2@Z1@F%2Z2@Z1@F%1Z2@Z1@F%0Z2@3fooMFNaNfZv This is a bit longer than the binary compression, but should be about the same when base64 encoding is applied to the latter. Please also note that the encoding has strictly linear size, while the binary compression is limited to a constant factor by maximum encodable match length and dictionary size. Starting with a recursion depth of 16, compiling for win64 crashes the compiler (issue 16229) Starting with a recursion depth of 19, the current compiler also bails out with testexpansion.d(6): Error: function testexpansion.s!(Result).s excessive length 66394404789887526 for symbol, possible recursive expansion? Compilation of the example for win32 with recursion depth 18 takes 3.1 seconds with the current mangling, but is hardly measurable with the mangling in PR 5855.

> For anyone who want to try a new scheme for reducing the symbol size: have a look at the test case for issue 16039 where a simple change makes the binary size explode from 18MB to over 400MB. With https://github.com/dlang/dmd/pull/5904 applied to avoid the crash when building for Win64, I get a 250 MB object file. With PR https://github.com/dlang/dmd/pull/5855, it shrinks to 645 kB.

Thanks, Rainer! That's really great. What's left to be done, apart from PR 5904, before PR 5855 can be merged?

> What's left to be done, apart from PR 5904, before PR 5855 can be merged? The PR fails because it seems there are some issues with building shared libraries. In addition, a number of compiler tests and unittests check the current mangling explicitely, so these have to be adjusted. I'm not sure how useful these tests are, maybe they should check the mangle-demangle pair instead. Unfortunately, changing the mangling is a not-so-small breaking change that affects a number of functions in druntime and phobos (e.g. demangle, core.internal.traits.externDFunc and std.traits.mangledName) that don't have a feasable replacement yet (my best guess is to add some __trait). It's also possible that people have taken advantage of the current mangling in their code. In addition, we should verify a new mangling addresses reported ambiguities of the existing mangling.

(In reply to Rainer Schuetze from comment #10) > The PR fails because it seems there are some issues with building shared > libraries. This is something I can't really help, but maybe we can enlist some experts from the forums. > In addition, a number of compiler tests and unittests check the > current mangling explicitely, so these have to be adjusted. I'm not sure how > useful these tests are, maybe they should check the mangle-demangle pair > instead. Since the mangling is part of the ABI, I think it's valid to check for them. Perhaps what we need is a versioned-out version that checks for your expected mangling, and then when we "flip the switch" we can switch to that version. > Unfortunately, changing the mangling is a not-so-small breaking change that > affects a number of functions in druntime and phobos (e.g. demangle, > core.internal.traits.externDFunc and std.traits.mangledName) that don't have > a feasable replacement yet (my best guess is to add some __trait). Again, we should use versioned code. The D compiler can define whether the new mangling scheme is enabled or not. > It's also possible that people have taken advantage of the current mangling > in their code. This is something we can't really help. However, I highly doubt that anyone is taking advantage of giant voldemort symbol names. Mangling is something I doubt we can deprecate. However, their code could employ the version scheme to at least avoid expectations that won't be met. > In addition, we should verify a new mangling addresses reported ambiguities > of the existing mangling. Links? (In reply to ZombineDev from comment #9) > Thanks, Rainer! That's really great. +100, this is awesome work!

(In reply to Steven Schveighoffer from comment #11) > Since the mangling is part of the ABI, I think it's valid to check for them. > Perhaps what we need is a versioned-out version that checks for your > expected mangling, and then when we "flip the switch" we can switch to that > version. I started to just allow both versions in the tests, but that started to spread across a lot of files. Versioning on some condition should be ok, too. > However, I highly doubt that anyone > is taking advantage of giant voldemort symbol names. Mangling is something I > doubt we can deprecate. However, their code could employ the version scheme > to at least avoid expectations that won't be met. The decision cannot be made just for user code, phobos and druntime must be compiled with the same mangling. > > In addition, we should verify a new mangling addresses reported ambiguities > > of the existing mangling. > > Links? I skipped over a search for "mangling" and "mangl" in bugzilla: Trouble with scoped variables/functions: - Issue 4699 - Functions in peer scopes cannot have the same name - Issue 14831 - Each function local symbols should have unique mangled name Ambiguous name mangling: - Issue 3043 - Template symbol arg cannot be demangled - Issue 5957 - Ambiguous mangling of module and template in template symbol args - Issue 6525 - Numeric literals should always be mangled with a leading 'i' - Issue 6526 - Disambiguate mangling of AA literals - Issue 6527 - Ambiguous mangling of inout parameters - Issue 11273 - inequable template alias parameters can be mangled identically - Issue 14576 - [ddemangle] core.demangle unable to handle ambiguity in symbols Bogus mangling/demangling: - Issue 8789 - mangling of const member function - Issue 14319 - core.demangle does not support member function attributes - Issue 14563 - core.demangle: Does not demangle type modifers - Issue 10393 - demangle doesn't work for unicode symbol names - Issue 14410 - core.demangle doesn't handle typeof(null) correctly - Issue 11131 - variables without linkage shouldn't have a mangling (.mangleof) - Issue 11248 - template value parameter cause too long mangling - Issue 14894 - mangling of mixins and lambdas can change w/ -unittest or other versions Compiler generated special symbols don't follow the ABI: - Issue 5644 - The mangling of constructors is not documented by the ABI - Issue 6045 - Unable to demangle symbols - Issue 11586 - core.demangle should understand _D16TypeInfo_HAyayAa6__initZ etc. - Issue 10189 - demangle doesn't work with __ModuleInfoZ __initZ __arrayZ Different number of underscores for _D: - Issue 8207 - OS X: Should extern(D) symbols include another underscore? - Issue 15748 - inconsistent symbols generated by dmd vs ldc

It's an important issue and should be addressed. Let's work on that for 2.073 which is scheduled for the end of 2016. Because this will impact many tools in D's ecosystem, we need to proper plan how to mitigate the impact. A few points. - Need to talk to Iain to update gdb's D demangler. This will take ages to upstream and end up in distributions. Maybe we can should the backref mangling to only very long names in the beginning? Those are unreadable already and not showing them would rather fix a few GUIs. - Should we also try to address other mangling issues? Some things like the ambiguity are annoying but not that problematic. Also mixing in other changes will only increase the impact and make it harder to release. FWIW this is also not a "new" mangling but an abbreviation of the existing one. - We need to fix all our toolings and libraries. There are some functions in druntime&phobos that build mangled names (e.g. for loading shared library symbols). At best we can just implement the backref scheme in core.demangle.mangle and reuse the in phobos. We also ship the ddemangle tool and there are other debuggers (at least the maintained ones need updates). - OT: I'd like to see a similar abbreviation scheme for core.demangle.demangle, b/c the full template names in backtraces aren't readable either. Would be nicer to have something along the line of `func!(Symbol!(Foo, @2))`.

For stack trace it should be enough (for this example) mymodule.s.Result.foo without parameters even, file and line number should be enough to locate it.

(In reply to anonymous4 from comment #14) > For stack trace it should be enough (for this example) mymodule.s.Result.foo > without parameters even, file and line number should be enough to locate it. Let's continue that part of the discussion in issue 14885. We really just need someone to spec a feasible implementation.

Commits pushed to mangle at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/60022cb0ed949f5f6bca2a588e1b00a638b48767 fix issue 15831: mangle back references for types and identifiers https://github.com/dlang/dmd/commit/16101ef1f48fd9b32d1b2f16e07eb3ee4c7a2c60 Merge pull request #5855 from rainers/mangle_backrefs fix Issue 15831 - Mangle back references to avoid huge symbol names merged-on-behalf-of: unknown

Reopening as the changes to dmd and druntime haven't landed on the master branch, but on the mangle experimental branch.

Commit pushed to master at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/c272eb830597efcc8fe75c7e1c9791c512a08727 fix issue 15831: mangle back references for types and identifiers

Commit pushed to stable at https://github.com/dlang/dmd https://github.com/dlang/dmd/commit/c272eb830597efcc8fe75c7e1c9791c512a08727 fix issue 15831: mangle back references for types and identifiers