[analyzer][ctu] Fix wrong 'multiple definitions' errors caused by space characters in lookup names when parsing the ctu index file

[OikawaKirie]

Summary

This error was found when analyzing MySQL with CTU enabled.

When there are space characters in the lookup name, the current delimiter searching strategy will make the file path wrongly parsed.
And when two lookup names have the same prefix before their first space characters, a 'multiple definitions' error will be wrongly reported.

e.g. The lookup names for the two lambda exprs in the test case are c:@S@G@F@G#@Sa@F@operator int (*)(char)#1 and c:@S@G@F@G#@Sa@F@operator bool (*)(char)#1 respectively. And their prefixes are both c:@S@G@F@G#@Sa@F@operator when using the first space character as the delimiter.

Solving the problem by adding a length for the lookup name, making the index items in the format of <USR-Length>:<USR File> <Path>.

---

In the test case of this patch, we found that it will trigger a "triple mismatch" warning when using clang -cc1 to analyze the source file with CTU using the on-demand-parsing strategy in Darwin systems. And this problem is also encountered in D75665, which is the patch introducing the on-demand parsing strategy.
We temporarily bypass this problem by using the loading-ast-file strategy.

Refer to the discourse topic for more details.

[steakhal]

I don't really like having multiple files with the same name.
And the importer TU should be simple to be simply cat-ed into a temporal file.
At that point, you could put the importee's content into this file. It would result in a single, self-contained test case.

I'm not really familiar with the extdefmap part, but I'm surprised that we are using spaces as separators.
Shouldn't we consider using a different character?

clang/test/Analysis/ctu-lookup-name-with-space.cpp

8

Probably splitting this up into multiple lines would result in a more readable solution.

Something along these lines should work:

cat >%t/compile_commands.json <<EOL
line 1
line 2
...
EOL

12–24

Why do you need two separate invocations? Couldn't you just merge these?
I've seen cases where -verify was used in conjunction with FileCheck.

[OikawaKirie]

In D102669#2765233, @steakhal wrote:

I'm not really familiar with the extdefmap part, but I'm surprised that we are using spaces as separators.
Shouldn't we consider using a different character?

I prefer the idea of changing the delimiter character, but it may lead to modifying a lot of test cases.
I think we'd better make this change in another revision in the future if we do want to change it.

clang/test/Analysis/ctu-lookup-name-with-space.cpp

8

The suggestion is great, however I cannot find a way to write the RUN commands.
Could you please tell me how to write the commands in this way? It is also useful to help me merging the test case into one file.

12–24

I forgot the --allow-empty argument during writing this test case. I will merge them in an update.

[martong]

First of all, thank you for the patch!

We had a meeting with my colleges (@steakhal, @gamesh411) and we agreed in the following. This issue you are trying to solve here is indeed a serious problem, but we'd like to suggest an alternative and perhaps more durable solution. In CrossTranslationUnitContext::getLookupName(const NamedDecl *ND) it would be possible to extend the returned string with a prefix that encodes the length of the USR string.
So, instead of

c:@F@g#I# ctu-other.cpp.ast

we'd get

9:c:@F@g#I# ctu-other.cpp.ast

This way, we could handle even file names with spaces in them.

[steakhal]

There are quite a few places where the extdef mappings should be updated.
For discovering them I suggest you asserting the new file format (only for detecting them!). This way if you miss one, it wouldn't silently 'work' somehow, but raise your attention.

There are a few references to the format of this mapping in the clang/docs/analyzer/user-docs/CrossTranslationUnit.rst and probably in other files.
Those should be updated to match the new format.

I'm sorry for burdening you with all of this, but I think this is the way to make this parsing more robust. I really appreciate your work.

[OikawaKirie]

It has been a long period since the last discussion, I hope you can still remember this bug. And apologize for the delay.

Updated as required, the lookup name generator CrossTranslationUnitContext::getLookupName and parser parseCrossTUIndex are modified.
And assertions are added before accessing the CTU index mapping for input lookup names to be searched.

Corresponding test cases and documents are also updated.

Please let me know if there are other files to be updated.

[steakhal]

Looks good.
Please get rid of the macro stuff, consider something along the lines I proposed for the parsing stuff.
Also clang-format the code you touch.
I haven't checked the docs and the comments of the codebase, but I'll assume you grepped and fixed all occurrences.
I look forward to this, thank you for working on this @OikawaKirie.

clang/docs/analyzer/user-docs/CrossTranslationUnit.rst

84

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

175–180

Please do something about this macro.
Encapsulate the logic in some other way.

460

clang/test/Analysis/func-mapping-test.cpp

50–62

I think you could add your lambda stuff to this file.
This is really the place for testing this.
The test you created actually demonstrating the CTU issue is also valuable IMO, so you can leave it, but have a copy here.

[OikawaKirie]

1. Fix formatting bugs
2. Update lookup name format as <USR-Length>:<USR> <File-Path> in all comments and documents
3. Add the new test case as a part of clang/test/Analysis/func-mapping-test.cpp to verify the lookup name
4. Change the macros for asserting the lookup name format to an NDEBUG wrapped function

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

The source of lookup name of the function being imported is function CrossTranslationUnitContext::getLookupName. Keeping the length in the mapping can avoid parsing the lookup name during importing.

[steakhal]

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

Okay; you can copy the original StringRef to have that. But by consuming it on one path makes the code much more readable.

183

charactor -> character

184–188

You should probably use more elaborative names, I wouldn't know what this does if I hadn't reviewed this patch.

450

The assertion speaks for itself. It rarely needs additional documentation.

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

8–9

I would rather put these into the importee()

14

Why do you need to have a div by zero warning?

[OikawaKirie]

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

The getAsInterger call can also check whether the content before the first colon is an integer. Therefore, a sub-string operation is required here.

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

8–9

The lambda exprs will not be included in the CTU index file if they are declared in a normal function.

14

I am not sure whether we should test if an external function can be correctly imported. Hence, I wrote a div-by-zero bug here. A call to function clang_analyzer_warnIfReached is also OK here.

As the imported lambda expr will not be called, I think I can only test whether CTU works via another normal function.

[steakhal]

Please mark comments 'done' if they are done.

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

I don't doubt that your proposed way of doing this works and is efficient.
What I say is that I think there is room for improvement in the non-functional aspects, in the readability. However, it's not really a blocking issue, more of a personal taste.

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

8–9

I see.

14

AFAIK importing a function and import-related stuff are orthogonal to actually emitting bug reports produced by the analyzer. That being said, if the importee() would have an empty body, the observable behavior would remain the same. And this is what I propose now.

[OikawaKirie]

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

I know what you are considering, it is clearer and more readable by consuming the length, then the USR. However, to correctly separate the USR and file path, the length of USR-Length is also required, which makes it impossible to just *consume* the length at the beginning.

Another way of solving this problem is to re-create the string with the USR-Length and the USR after parsing, but I think it is not a good solution.

BTW, is it necessary to assert the USR-Length to be greater than zero? I think it is more reasonable to report *invalid format* rather than assert the value, as it can be provided by the user.

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

14

Sorry, but I am not quite clear about your suggestions on this function.

[steakhal]

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

I think what causes the misunderstanding is the definition of consume in the context of StringRef.

const StringRef Copy = Line;
Line.consumeInteger(...); // Line advances forward by the number of characters that were parsed as an integral value.
// Copy still refers to the unmodified, original characters.
// I can use it however I want.

// `Line` is a suffix of `Copy`, and the `.end()` should be the same, only `.begin()` should differ.

I hope that caused the miscommunication.

---

BTW, is it necessary to assert the USR-Length to be greater than zero? I think it is more reasonable to report *invalid format* rather than assert the value, as it can be provided by the user.

Yeah, sure!

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

13–15

Also fixup the return type in the declaration within the main TU. Also add the // expected-no-diagnostics comment to the primary TU.

[OikawaKirie]

clang/lib/CrossTU/CrossTranslationUnit.cpp

154–172

I think I have figured out what have been misunderstood.

In the current patch, I just modify function CrossTranslationUnitContext::getLookupName by adding a length at the beginning. Therefore, the lookup name for the CTU query will have the length part. And for the sake of simplicity and efficiency, the length together with the USR is stored in the mapping as the key.

To correctly parse the <USR-Length>:<USR> part, I cannot just consume the <USR-Length> at the beginning. Otherwise, I cannot know the length of <USR-Length>: part, which makes it impossible to parse the entire <USR-Length>:<USR> part, even though the original Line is copied.

I will update the approach of adding the length part. Since the length is only used during parsing the CTU index, I will modify function createCrossTUIndexString to add the length and revert the changes to function CrossTranslationUnitContext::getLookupName to keep the lookup name for CTU query unchanged.

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

13–15

Yes, you are right.
I was misled by myself.

[OikawaKirie]

1. Revert function CrossTranslationUnitContext::getLookupName
2. Add length when dumping the CTU index mapping via function createCrossTUIndexString
3. Remove the assertions during CTU map query process
4. Make function parseCrossTUIndexItem more readable

[steakhal]

I think it looks great. Thanks.

[OikawaKirie]

When running my test case ctu-lookup-name-with-space.cpp on Windows, llvm-lit reports 'cp': command not found. And this is the reason why it fails on Windows.
And when I remove the cps and replace them with original file names, clang reports YAML:1:293: error: Unrecognized escape code, it seems that the static analyzer only reads compilation database in YAML format on Windows.
Should I disable this test case on Windows? Or is there any other approaches to make it work on Windows?

[steakhal]

In D102669#3194405, @OikawaKirie wrote:

Should I disable this test case on Windows? Or is there any other approaches to make it work on Windows?

I'm fine with disabling this test on Windows.

[OikawaKirie]

Fix YAML:1:293: error: Unrecognized escape code error by replacing lit substitution pattern %S to %/S.
Fix cp problems by removing the file copy operations.

[OikawaKirie]

It seems this patch has nothing to do with the failure in the Linux build. I think it is now ready to land.
Thanks a lot for your suggestions during the revision.

Could you please commit this patch on my behalf? Thanks.
Ella Ma <[e-mail]>

[ahatanak]

This commit seems to have caused a test to fail: https://green.lab.llvm.org/green/job/clang-stage1-cmake-RA-incremental/26118/testReport/

Can you fix the failure or revert the patch?

[OikawaKirie]

I do not know how this error happens. Maybe we can currently revert this patch an have another try in the future.

[thakis]

This breaks tests on macOS: http://45.33.8.238/macm1/23920/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[OikawaKirie]

Could you please revert this on my behalf? I currently have no idea to fix this problem.

[thakis]

reverted in 770ef94097c02205b3ec9e902f1d6a9c99b5189c. thanks!

[OikawaKirie]

It seems that it is not this patch that triggers the problem, which is similar to D75665.
IMO it is the problem of on-demand-parsing, but I do not have a Mac M1 device to reproduce this bug.
Maybe we can just land this patch by restricting the test case to be executed only on Linux, just as what D75665 does (rG5cc18516c483 vs rG97e07d0c352c), and leave the problem for future fixes.

Could you please do the update as provided below and land this patch again? @steakhal or other reviewers?

clang/test/Analysis/ctu-lookup-name-with-space.cpp

13

Adding this line here.

[steakhal]

We shouldn't skip mac targets. I CC ASTImporter folks, they probably have an M1.

[arichardson]

clang/test/Analysis/ctu-lookup-name-with-space.cpp

13

Disabling the test on non- Linux is not a good idea IMO since it means we lose coverage on other platforms. My guess is that you just need to specify an explicit triple in the clang invocations.

[OikawaKirie]

In D102669#3199270, @steakhal wrote:

We shouldn't skip mac targets. I CC ASTImporter folks, they probably have an M1.

I am not intended to ignore this problem triggered on M1. However, I think it is not this patch that leads to this problem, it just triggers it.
I mean we can just disable the test case temporarily on M1, and fix this problem as well as enable this patch and the one of on-demand-parsing in another patch.
I think they trigger the same problem for the same reason on M1.

Besides, it seems to be the problem of ASTUnit::LoadFromCommandLine, rather than the ASTImporter.

clang/test/Analysis/ctu-lookup-name-with-space.cpp

13

AFAIK, we cannot do that. If this test case is executed on different platforms, we cannot determine the triple ahead of time and specify it in the invocation list.

[steakhal]

In D102669#3205889, @OikawaKirie wrote:

In D102669#3199270, @steakhal wrote:

We shouldn't skip mac targets. I CC ASTImporter folks, they probably have an M1.

I am not intended to ignore this problem triggered on M1. However, I think it is not this patch that leads to this problem, it just triggers it.
I mean we can just disable the test case temporarily on M1, and fix this problem as well as enable this patch and the one of on-demand-parsing in another patch.
I think they trigger the same problem for the same reason on M1.

Besides, it seems to be the problem of ASTUnit::LoadFromCommandLine, rather than the ASTImporter.

Prior to this patch, it worked on M1; after landing it broke something, so we clearly shouldn't land this.
We should add a test-case demonstrating the problem with M1 with a given configuration.
Then we need to track down and fix the underlying issue causing it. That should be done probably in a separate patch and add it as a parent patch to this one.

If all of these are done, we can probably land both of them.

clang/test/Analysis/ctu-lookup-name-with-space.cpp

13

If we were to pin the triple, then each platform would emit the correct AST dumps according to that platform - ~~ cross-compilation.

[OikawaKirie]

In D102669#3206089, @steakhal wrote:

Prior to this patch, it worked on M1; after landing it broke something, so we clearly shouldn't land this.

I do not think it is this patch that breaks the functionality on M1, as it depends on the *on-demand-parsing* feature that is not tested on M1 currently.

We should add a test-case demonstrating the problem with M1 with a given configuration.

If I got it correct (it is on-demand-parsing that triggers the problem), this problem can be triggered by enabling the test case of D75665 on M1.

Then we need to track down and fix the underlying issue causing it. That should be done probably in a separate patch and add it as a parent patch to this one.

If all of these are done, we can probably land both of them.

Maybe currently a simpler way is trying to use AST dump to load the external TU to be imported, rather than on-demand-parsing, which can make us fix this failure with the test case still enabled on M1.

I will have a series of tests on my concerns later, and I will reply with my results if I can find something.

[OikawaKirie]

I have confirmed that this problem is not due to this patch.
Besides, on Mac, both m1 and intel, the on-demand-parsing as well as loading an AST file generated via driver argument -emit-ast will also trigger this problem.
However, when loading an AST file generated via cc1 argument -emit-pch, the problem is not triggered.

---

See the example below, which is executed on an intel Mac laptop with clang 13.0.0.

/tmp/test/test.c:

void f();
void g() { f(); }

/tmp/test/importee.c:

void f() { }

/tmp/test/odp/externalDefMap.txt:

c:@F@f /tmp/test/importee.c

/tmp/test/odp/invocations.yaml:

"/tmp/test/importee.c": ["gcc", "-c", "/tmp/test/importee.c"]

/tmp/test/ast/externalDefMap.txt:

c:@F@f /tmp/test/ast/importee.c.ast

When executing the analyzer with CTU analysis via on-demand-parsing:

/tmp/test$ clang -cc1 -analyze -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=odp,ctu-invocation-list=invocations.yaml test.c

Or loading AST file generated via driver argument -emit-ast:

/tmp/test$ clang -emit-ast importee.c -o ast/importee.c.ast
/tmp/test$ clang -cc1 -analyze -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=ast test.c

The same diagnostic message is generated, though the triples are different from the ones for m1.

warning: imported AST from '/tmp/test/importee.c' had been generated for a different target, current: x86_64-apple-darwin21.2.0, imported: x86_64-apple-macosx12.0.0 [-Wctu]

---

However, the problem will not be triggered if triple is given:
(On demand parsing: setting the triple of the entry file to the one of imported ASTUnit)

/tmp/test$ clang -cc1 -analyze -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=odp,ctu-invocation-list=invocations.yaml test.c -triple x86_64-apple-macosx12.0.0

(AST)

/tmp/test$ clang -target arm-apple-macosx -emit-ast importee.c -o ast/importee.c.ast
/tmp/test$ clang -cc1 -analyze -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=ast test.c -triple arm-apple-macosx

Or the AST file is generated via cc1 argument -emit-pch:

/tmp/test$ clang -cc1 -emit-pch importee.c -o ast/importee.c.ast
/tmp/test$ clang -cc1 -analyze -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=ast test.c

I think we can bypass the problem temporarily by loading the AST file generated by cc1 argument -emit-pch, just as shown in the last code snippet above.

[OikawaKirie]

Replace on-demand-parsing with loading AST file for the new test case.
Tested on Linux and MacOS(x86).
If it can also pass the CI test on Windows, I think we can have another try on landing this patch.

Besides, as mentioned above, to trigger the problem of target triple on MacOS, we can simply remove the requirement of Linux system for the two test cases of on-demand-parsing, i.e. clang/test/Analysis/ctu-on-demand-parsing.c and clang/test/Analysis/ctu-on-demand-parsing.cpp.

[OikawaKirie]

To make it work on Windows, Linux, and Mac OS, using echo to create the external function map, and using AST file for CTU analysis.
Tested on Windows, Linux, and Mac OS under x64.

[OikawaKirie]

I think I have found out the reason for the problem, and it proved my guesses.

When executing the test case of the static analyzer, we usually use %clang_analyze_cc1 as the entry, which is %clang_cc1 -analyze. And we usually do not set a target triple, as it is not required by the analyzer. However, things are complicated in Darwin Unix.

In Darwin, the default target triple is ARCH-apple-darwinXX.XX.XX, where ARCH is the architecture (e.g. x86_64) and XX.XX.XX is the version of the Darwin system. And the default target triple will be then adjusted to ARCH-apple-SYSTEMXX.XX.XX by the Driver::Darwin::ComputeEffectiveClangTriple in driver related code, where SYSTEM can be watchos, tvos, ios and macosx.

In the clang driver, the adjusted target triple will be passed to the new cc1 process; whereas in tooling and ASTUnit::LoadFromCommandLine, the adjusted target triple will be used to generate cc1 arguments to create CompilerInvocation. But when executing bare clang -cc1, if the target triple argument is not provided, it remains the default ARCH-apple-darwinXX.XX.XX. And this is the reason for the conflict.

The CTU on-demand-parsing mechanism uses ASTUnit::LoadFromCommandLine to load external ASTs. The tool clang-check uses clang tooling to parse the entry file. Therefore, both target triples are the adjusted ones, which can be matched. And so is the driver (clang --analyze ...). But not the bare %clang_cc1, its target triple is the default one.

---

Let's have a look at the simple example, suppose externalDefMap.txt and invocations.yaml are generated correctly.

input.cc:

void bar();
void foo() { bar(); }

importee.cc:

void bar() { }

---

Using driver:

clang -v --analyze input.cc -Xanalyzer -analyzer-config -Xanalyzer experimental-enable-naive-ctu-analysis=true,ctu-dir=.

Output: OK, adjusted to adjusted

(in-process)
/path/to/clang-15 -cc1 -triple x86_64-apple-macosx10.15.0 ...

---

Using clang-check:

clang-check -analyze input.cc -- -v -Xanalyzer -analyzer-config -Xanalyzer experimental-enable-naive-ctu-analysis=true,ctu-dir=.

Output: OK, adjusted to adjusted

clang Invocation:
 "/path/to/clang-tool" "-cc1" "-triple" "x86_64-apple-macosx10.15.0"

---

Using cc1:

clang -cc1 -v -analyze input.cc  -analyzer-checker=core -analyzer-config experimental-enable-naive-ctu-analysis=true,ctu-dir=.

Output: ERROR, default to adjusted

warning: imported AST from 'importee.cc' had been generated for a different target, current: x86_64-apple-darwin19.6.0, imported: x86_64-apple-macosx10.15.0 [-Wctu]

---

What do you think is a better way to fix this problem? @gamesh411 @steakhal @martong
Using clang-check to run the test case seems to be a good way to overcome the problem, but the problem still exists.
However, IMO it is not a good idea to make clang cc1 to adjust the default target triple manually.

[steakhal]

Thank you @OikawaKirie for the thorough investigation and explanation, even annotations and examples. I really appreciate it.
However, you already surpassed my knowledge regarding the frontend, cc1, and other driver magic transformations.

I think it would be great to invite some Apple folks and experts in the driver flag stuff. That being said this interesting behavior would be a nice candidate for a post on the clang discourse forum.
@NoQ might also have something to say about this target triple magic.

[steakhal]

Hi @keith, I've seen you commented on a clang driver-related issue: "Why does march=native not work on Apple M1?"
You might also have some valuable insight about this weird behavior about the detected target triple in a regular mode and using the -cc1 mode.
You don't need to go through the whole conversation, the last few comments should be enough.
Feel free to invite more people if you think.

[keith]

In D102669#3325467, @steakhal wrote:

Hi @keith, I've seen you commented on a clang driver-related issue: "Why does march=native not work on Apple M1?"
You might also have some valuable insight about this weird behavior about the detected target triple in a regular mode and using the -cc1 mode.
You don't need to go through the whole conversation, the last few comments should be enough.
Feel free to invite more people if you think.

I'm not very familiar with the logic or history here, but I did look into this a bit, and I don't see a clear solution. I think the logic that lives in the Darwin driver code for creating the triple would have to be called from the default triple logic that's used in the cc1 case. I imagine to make this test pass you'd be best off making sure you always call clang or cc1, and not intermix them, or provide a default triple in all cases that's stable if possible. I do think it would be nice to unify the triple logic between these 2 places, but I imagine folks who know this code better than I do have opinions there.

[OikawaKirie]

Thanks, @keith.

I agree with @keith to commit this patch without using on-demand-parsing through cc1.
As this patch has nothing to do with the target triple issue we found.

In the current version, I use the PCH file to load the external TU.
And it seems to work fine on my system and on the Windows CI.

IMO, maybe we can just leave a FIXME or something else in the test case and commit this patch to fix the original problem we want to fix.
(of course, re-submit to rerun the test case on Linux)
What do you think? @steakhal

[steakhal]

In D102669#3395364, @OikawaKirie wrote:

IMO, maybe we can just leave a FIXME or something else in the test case and commit this patch to fix the original problem we want to fix.
(of course, re-submit to rerun the test case on Linux)
What do you think? @steakhal

I agree.
Please update the summary to have a reference to the discourse question you posted about this.

[OikawaKirie]

• Add FIXME in test case.
• Add discourse topic link in summary.

[steakhal]

Okay, let's give it another shot. Please monitor any buildbot failures and revert promptly if needed.

clang/docs/analyzer/user-docs/CrossTranslationUnit.rst

.. code-block:: bash
   $ pwd $ /path/to/your/project
   $ clang++ -emit-ast -o foo.cpp.ast foo.cpp
   $ # Check that the .ast file is generated:
   $ ls
   compile_commands.json  foo.cpp.ast  foo.cpp  main.cpp
   $
 
 The next step is to create a CTU index file which holds the `USR` name and location of external definitions in the
-source files:
+source files in format `<USR-Length>:<USR> <File-Path>`:
 
 .. code-block:: bash
 
   $ clang-extdef-mapping -p . foo.cpp
-  c:@F@foo# /path/to/your/project/foo.cpp
+  9:c:@F@foo# /path/to/your/project/foo.cpp
   $ clang-extdef-mapping -p . foo.cpp > externalDefMap.txt
 
 We have to modify `externalDefMap.txt` to contain the name of the `.ast` files instead of the source files:
 
 .. code-block:: bash
 
   $ sed -i -e "s/.cpp/.cpp.ast/g" externalDefMap.txt
 
"/path/to/your/project/main.cpp":
     - "clang++"
     - "-c"
     - "/path/to/your/project/main.cpp"
     - "-o"
     - "/path/to/your/project/main.o"
 
 We'd like to analyze `main.cpp` and discover the division by zero bug.
 As we are using On-demand mode, we only need to create a CTU index file which holds the `USR` name and location of
-external definitions in the source files:
+external definitions in the source files in format `<USR-Length>:<USR> <File-Path>`:
 
 .. code-block:: bash
 
   $ clang-extdef-mapping -p . foo.cpp
-  c:@F@foo# /path/to/your/project/foo.cpp
+  9:c:@F@foo# /path/to/your/project/foo.cpp
   $ clang-extdef-mapping -p . foo.cpp > externalDefMap.txt
 
 Now everything is available for the CTU analysis.
 We have to feed Clang with CTU specific extra arguments:
 
 .. code-block:: bash
 
   $ pwd

clang/include/clang/Basic/DiagnosticCrossTUKinds.td

 //==--- DiagnosticCrossTUKinds.td - Cross Translation Unit diagnostics ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 let Component = "CrossTU" in {
 
 def err_ctu_error_opening : Error<
   "error opening '%0': required by the CrossTU functionality">;
 
 def err_extdefmap_parsing : Error<
-  "error parsing index file: '%0' line: %1 'UniqueID filename' format "
-  "expected">;
+  "error parsing index file: '%0' line: %1 '<USR-Length>:<USR> <File-Path>' "
+  "format expected">;
 
 def err_multiple_def_index : Error<
   "multiple definitions are found for the same key in index ">;
 
 def warn_ctu_incompat_triple : Warning<
   "imported AST from '%0' had been generated for a different target, "
   "current: %1, imported: %2">, InGroup<CrossTU>;
 }

clang/lib/CrossTU/CrossTranslationUnit.cpp

 void IndexError::log(raw_ostream &OS) const {
   OS << Category->message(static_cast<int>(Code)) << '\n';
 }
 
 std::error_code IndexError::convertToErrorCode() const {
   return std::error_code(static_cast<int>(Code), *Category);
 }
 
+/// Parse one line of the input CTU index file.
+///
+/// @param[in]  LineRef     The input CTU index item in format
+///                         "<USR-Length>:<USR> <File-Path>".
+/// @param[out] LookupName  The lookup name in format "<USR-Length>:<USR>".
+/// @param[out] FilePath    The file path "<File-Path>".
+static bool parseCrossTUIndexItem(StringRef LineRef, StringRef &LookupName,
+                                  StringRef &FilePath) {
+  // `LineRef` is "<USR-Length>:<USR> <File-Path>" now.
+
+  size_t USRLength = 0;
+  if (LineRef.consumeInteger(10, USRLength))
+    return false;
+  assert(USRLength && "USRLength should be greater than zero.");
+
+  if (!LineRef.consume_front(":"))
+    return false;
+
+  // `LineRef` is now just "<USR> <File-Path>".
+
+  // Check LookupName length out of bound and incorrect delimiter.
+  if (USRLength >= LineRef.size() || ' ' != LineRef[USRLength])
+    return false;
+
+  LookupName = LineRef.substr(0, USRLength);
+  FilePath = LineRef.substr(USRLength + 1);
+  return true;
+}
+
 llvm::Expected<llvm::StringMap<std::string>>
 parseCrossTUIndex(StringRef IndexPath) {
   std::ifstream ExternalMapFile{std::string(IndexPath)};
   if (!ExternalMapFile)
     return llvm::make_error<IndexError>(index_error_code::missing_index_file,
                                         IndexPath.str());
 
   llvm::StringMap<std::string> Result;
   std::string Line;
   unsigned LineNo = 1;
   while (std::getline(ExternalMapFile, Line)) {
-    StringRef LineRef{Line};
-    const size_t Delimiter = LineRef.find(' ');
-    if (Delimiter > 0 && Delimiter != std::string::npos) {
-      StringRef LookupName = LineRef.substr(0, Delimiter);
+    // Split lookup name and file path
+    StringRef LookupName, FilePathInIndex;
+    if (!parseCrossTUIndexItem(Line, LookupName, FilePathInIndex))
+      return llvm::make_error<IndexError>(
+          index_error_code::invalid_index_format, IndexPath.str(), LineNo);
 
-      // Store paths with posix-style directory separator.
-      SmallString<32> FilePath(LineRef.substr(Delimiter + 1));
-      llvm::sys::path::native(FilePath, llvm::sys::path::Style::posix);
+    SmallString<32> FilePath(FilePathInIndex);
 
-      bool InsertionOccured;
-      std::tie(std::ignore, InsertionOccured) =
-          Result.try_emplace(LookupName, FilePath.begin(), FilePath.end());
-      if (!InsertionOccured)
-        return llvm::make_error<IndexError>(
-            index_error_code::multiple_definitions, IndexPath.str(), LineNo);
-    } else
-      return llvm::make_error<IndexError>(
-          index_error_code::invalid_index_format, IndexPath.str(), LineNo);
+
     ++LineNo;
   }
   return Result;
 }
 
 std::string
 createCrossTUIndexString(const llvm::StringMap<std::string> &Index) {
   std::ostringstream Result;
   for (const auto &E : Index)
-    Result << E.getKey().str() << " " << E.getValue() << '\n';
+    Result << E.getKey().size() << ':' << E.getKey().str() << ' '
+           << E.getValue() << '\n';
   return Result.str();
 }
 
 bool containsConst(const VarDecl *VD, const ASTContext &ACtx) {
   CanQualType CT = ACtx.getCanonicalType(VD->getType());
   if (!CT.isConstQualified()) {
     const RecordType *RTy = CT->getAs<RecordType>();
     if (!RTy || !RTy->hasConstFields())
if (ASTCacheEntry == FileASTUnitMap.end()) {
     return ASTCacheEntry->second.get();
   }
 }
 
 llvm::Expected<ASTUnit *>
 CrossTranslationUnitContext::ASTUnitStorage::getASTUnitForFunction(
     StringRef FunctionName, StringRef CrossTUDir, StringRef IndexName,
     bool DisplayCTUProgress) {
   // Try the cache first.
   auto ASTCacheEntry = NameASTUnitMap.find(FunctionName);
   if (ASTCacheEntry == NameASTUnitMap.end()) {
     // Load the ASTUnit from the pre-dumped AST file specified by ASTFileName.
 
     // Ensure that the Index is loaded, as we need to search in it.
     if (llvm::Error IndexLoadError =
             ensureCTUIndexLoaded(CrossTUDir, IndexName))
       return std::move(IndexLoadError);
 
-    // Check if there is and entry in the index for the function.
+    // Check if there is an entry in the index for the function.
     if (!NameFileMap.count(FunctionName)) {
       ++NumNotInOtherTU;
       return llvm::make_error<IndexError>(index_error_code::missing_definition);
     }
 
     // Search in the index for the filename where the definition of FuncitonName
     // resides.
     if (llvm::Expected<ASTUnit *> FoundForFile =

clang/test/Analysis/Inputs/ctu-import.c.externalDefMap.ast-dump.txt

-c:@F@testStaticImplicit ctu-import.c.ast
+23:c:@F@testStaticImplicit ctu-import.c.ast

clang/test/Analysis/Inputs/ctu-lookup-name-with-space.cpp

+void f(void (*)());
+void f(void (*)(int));
+
+struct G {
+  G() {
+    // multiple definitions are found for the same key in index
+    f([]() -> void {});    // USR: c:@S@G@F@G#@Sa@F@operator void (*)()#1
+    f([](int) -> void {}); // USR: c:@S@G@F@G#@Sa@F@operator void (*)(int)#1
+
+    // As both lambda exprs have the same prefix, if the CTU index parser uses
+    // the first space character as the delimiter between USR and file path, a
+    // "multiple definitions are found for the same key in index" error will
+    // be reported.
+  }
+};
+
+void importee() {}

clang/test/Analysis/Inputs/ctu-other.c.externalDefMap.ast-dump.txt

-c:@F@inlineAsm ctu-other.c.ast
-c:@F@g ctu-other.c.ast
-c:@F@f ctu-other.c.ast
-c:@F@enumCheck ctu-other.c.ast
-c:@F@identImplicit ctu-other.c.ast
-c:@F@structInProto ctu-other.c.ast
-c:@F@switchWithoutCases ctu-other.c.ast
+14:c:@F@inlineAsm ctu-other.c.ast
+6:c:@F@g ctu-other.c.ast
+6:c:@F@f ctu-other.c.ast
+14:c:@F@enumCheck ctu-other.c.ast
+18:c:@F@identImplicit ctu-other.c.ast
+18:c:@F@structInProto ctu-other.c.ast
+23:c:@F@switchWithoutCases ctu-other.c.ast

clang/test/Analysis/Inputs/ctu-other.cpp.externalDefMap.ast-dump.txt

-c:@N@chns@F@chf1#I# ctu-other.cpp.ast
-c:@N@myns@N@embed_ns@F@fens#I# ctu-other.cpp.ast
-c:@F@g#I# ctu-other.cpp.ast
-c:@S@mycls@F@fscl#I#S ctu-other.cpp.ast
-c:@S@mycls@F@fcl#I# ctu-other.cpp.ast
-c:@S@mycls@F@fvcl#I# ctu-other.cpp.ast
-c:@N@myns@S@embed_cls@F@fecl#I# ctu-other.cpp.ast
-c:@S@mycls@S@embed_cls2@F@fecl2#I# ctu-other.cpp.ast
-c:@S@derived@F@fvcl#I# ctu-other.cpp.ast
-c:@F@f#I# ctu-other.cpp.ast
-c:@N@myns@F@fns#I# ctu-other.cpp.ast
-c:@F@h#I# ctu-other.cpp.ast
-c:@F@h_chain#I# ctu-chain.cpp.ast
-c:@N@chns@S@chcls@F@chf4#I# ctu-chain.cpp.ast
-c:@N@chns@F@chf2#I# ctu-chain.cpp.ast
-c:@F@fun_using_anon_struct#I# ctu-other.cpp.ast
-c:@F@other_macro_diag#I# ctu-other.cpp.ast
-c:@extInt ctu-other.cpp.ast
-c:@N@intns@extInt ctu-other.cpp.ast
-c:@extS ctu-other.cpp.ast
-c:@S@A@a ctu-other.cpp.ast
-c:@extSC ctu-other.cpp.ast
-c:@S@ST@sc ctu-other.cpp.ast
-c:@extSCN ctu-other.cpp.ast
-c:@extSubSCN ctu-other.cpp.ast
-c:@extSCC ctu-other.cpp.ast
-c:@extU ctu-other.cpp.ast
-c:@S@TestAnonUnionUSR@Test ctu-other.cpp.ast
-c:@F@testImportOfIncompleteDefaultParmDuringImport#I# ctu-other.cpp.ast
-c:@F@testImportOfDelegateConstructor#I# ctu-other.cpp.ast
+19:c:@N@chns@F@chf1#I# ctu-other.cpp.ast
+30:c:@N@myns@N@embed_ns@F@fens#I# ctu-other.cpp.ast
+9:c:@F@g#I# ctu-other.cpp.ast
+21:c:@S@mycls@F@fscl#I#S ctu-other.cpp.ast
+19:c:@S@mycls@F@fcl#I# ctu-other.cpp.ast
+20:c:@S@mycls@F@fvcl#I# ctu-other.cpp.ast
+31:c:@N@myns@S@embed_cls@F@fecl#I# ctu-other.cpp.ast
+34:c:@S@mycls@S@embed_cls2@F@fecl2#I# ctu-other.cpp.ast
+22:c:@S@derived@F@fvcl#I# ctu-other.cpp.ast
+9:c:@F@f#I# ctu-other.cpp.ast
+18:c:@N@myns@F@fns#I# ctu-other.cpp.ast
+9:c:@F@h#I# ctu-other.cpp.ast
+15:c:@F@h_chain#I# ctu-chain.cpp.ast
+27:c:@N@chns@S@chcls@F@chf4#I# ctu-chain.cpp.ast
+19:c:@N@chns@F@chf2#I# ctu-chain.cpp.ast
+29:c:@F@fun_using_anon_struct#I# ctu-other.cpp.ast
+24:c:@F@other_macro_diag#I# ctu-other.cpp.ast
+9:c:@extInt ctu-other.cpp.ast
+17:c:@N@intns@extInt ctu-other.cpp.ast
+7:c:@extS ctu-other.cpp.ast
+8:c:@S@A@a ctu-other.cpp.ast
+8:c:@extSC ctu-other.cpp.ast
+10:c:@S@ST@sc ctu-other.cpp.ast
+9:c:@extSCN ctu-other.cpp.ast
+12:c:@extSubSCN ctu-other.cpp.ast
+9:c:@extSCC ctu-other.cpp.ast
+7:c:@extU ctu-other.cpp.ast
+26:c:@S@TestAnonUnionUSR@Test ctu-other.cpp.ast
+53:c:@F@testImportOfIncompleteDefaultParmDuringImport#I# ctu-other.cpp.ast
+39:c:@F@testImportOfDelegateConstructor#I# ctu-other.cpp.ast
 

clang/test/Analysis/Inputs/plist-macros-with-expansion-ctu.c.externalDefMap.txt

-c:@F@F1 plist-macros-ctu.c.ast
-c:@F@F2 plist-macros-ctu.c.ast
-c:@F@F3 plist-macros-ctu.c.ast
-c:@F@F_H plist-macros-ctu.c.ast
+7:c:@F@F1 plist-macros-ctu.c.ast
+7:c:@F@F2 plist-macros-ctu.c.ast
+7:c:@F@F3 plist-macros-ctu.c.ast
+8:c:@F@F_H plist-macros-ctu.c.ast

clang/test/Analysis/ctu-inherited-default-ctor.cpp

 // Should not crash with '-analyzer-opt-analyze-headers' option during CTU analysis.
 //
 // RUN: rm -rf %t && mkdir -p %t/ctudir
 // RUN: %clang_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -emit-pch -o %t/ctudir/ctu-inherited-default-ctor-other.cpp.ast \
 // RUN:    %S/Inputs/ctu-inherited-default-ctor-other.cpp
-// RUN: echo "c:@N@clang@S@DeclContextLookupResult@SingleElementDummyList ctu-inherited-default-ctor-other.cpp.ast" \
+// RUN: echo "59:c:@N@clang@S@DeclContextLookupResult@SingleElementDummyList ctu-inherited-default-ctor-other.cpp.ast" \
 // RUN:   > %t/ctudir/externalDefMap.txt
 //
 // RUN: %clang_analyze_cc1 -std=c++14 -triple x86_64-pc-linux-gnu \
 // RUN:   -analyzer-opt-analyze-headers \
 // RUN:   -analyzer-checker=core \
 // RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
 // RUN:   -analyzer-config ctu-dir=%t/ctudir \
 // RUN:   -analyzer-config display-ctu-progress=true \

clang/test/Analysis/ctu-lookup-name-with-space.cpp

+// RUN: rm -rf %t
+// RUN: mkdir %t
+
+// RUN: echo '"%/S/Inputs/ctu-lookup-name-with-space.cpp" : ["g++", "-c", "%/S/Inputs/ctu-lookup-name-with-space.cpp"]' > %t/invocations.yaml
+// RUN: %clang_extdef_map %S/Inputs/ctu-lookup-name-with-space.cpp -- > %t/externalDefMap.txt
+
+// RUN: cd %t && %clang_cc1 -fsyntax-only -analyze \
+// RUN:   -analyzer-checker=core,debug.ExprInspection \
+// RUN:   -analyzer-config experimental-enable-naive-ctu-analysis=true \
+// RUN:   -analyzer-config ctu-dir=. \
+// RUN:   -analyzer-config ctu-invocation-list=invocations.yaml \
+// RUN:   -verify %s
+
+void importee();
+
+void trigger() {
+  // Call an external function to trigger the parsing process of CTU index.
+  // Refer to file Inputs/ctu-lookup-name-with-space.cpp for more details.
+
+  importee(); // expected-no-diagnostics
+}

clang/test/Analysis/func-mapping-test.cpp

 // RUN: %clang_extdef_map %s -- | FileCheck --implicit-check-not "c:@y" --implicit-check-not "c:@z" %s
 
 int f(int) {
   return 0;
 }
-// CHECK-DAG: c:@F@f#I#
+// CHECK-DAG: 9:c:@F@f#I#
 
 extern const int x = 5;
-// CHECK-DAG: c:@x
+// CHECK-DAG: 4:c:@x
 
 // Non-const variables should not be collected.
 int y = 5;
 
 // In C++, const implies internal linkage, so not collected.
 const int z = 5;
 
 struct S {
   int a;
 };
 extern S const s = {.a = 2};
-// CHECK-DAG: c:@s
+// CHECK-DAG: 4:c:@s
 
 struct SF {
   const int a;
 };
 SF sf = {.a = 2};
-// CHECK-DAG: c:@sf
+// CHECK-DAG: 5:c:@sf
 
 struct SStatic {
   static const int a = 4;
 };
 const int SStatic::a;
-// CHECK-DAG: c:@S@SStatic@a
+// CHECK-DAG: 14:c:@S@SStatic@a
 
 extern int const arr[5] = { 0, 1 };
-// CHECK-DAG: c:@arr
+// CHECK-DAG: 6:c:@arr
 
 union U {
   const int a;
   const unsigned int b;
 };
 U u = {.a = 6};
-// CHECK-DAG: c:@u
+// CHECK-DAG: 4:c:@u
 
 // No USR can be generated for this.
 // Check for no crash in this case.
 static union {
   float uf;
   const int ui;
 };
+
+void f(int (*)(char));
+void f(bool (*)(char));
+
+struct G {
+  G() {
+    f([](char) -> int { return 42; });
+    // CHECK-DAG: 41:c:@S@G@F@G#@Sa@F@operator int (*)(char)#1
+    f([](char) -> bool { return true; });
+    // CHECK-DAG: 42:c:@S@G@F@G#@Sa@F@operator bool (*)(char)#1
+  }
+};

clang/unittests/CrossTU/CrossTranslationUnitTest.cpp

ASSERT_FALSE(
         llvm::sys::fs::createTemporaryFile("f_ast", "ast", ASTFD, ASTFileName));
     llvm::ToolOutputFile ASTFile(ASTFileName, ASTFD);
 
     int IndexFD;
     llvm::SmallString<256> IndexFileName;
     ASSERT_FALSE(llvm::sys::fs::createTemporaryFile("index", "txt", IndexFD,
                                                     IndexFileName));
     llvm::ToolOutputFile IndexFile(IndexFileName, IndexFD);
-    IndexFile.os() << "c:@F@f#I# " << ASTFileName << "\n";
+    IndexFile.os() << "9:c:@F@f#I# " << ASTFileName << "\n";
     IndexFile.os().flush();
     EXPECT_TRUE(llvm::sys::fs::exists(IndexFileName));
 
     StringRef SourceText = "int f(int) { return 0; }\n";
     // This file must exist since the saved ASTFile will reference it.
     int SourceFD;
     llvm::SmallString<256> SourceFileName;
     ASSERT_FALSE(llvm::sys::fs::createTemporaryFile("input", "cpp", SourceFD,