Index: clang-tools-extra/trunk/clangd/CodeComplete.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/CodeComplete.cpp
+++ clang-tools-extra/trunk/clangd/CodeComplete.cpp
@@ -327,8 +327,12 @@
       auto ResolvedInserted = toHeaderFile(Header, FileName);
       if (!ResolvedInserted)
         return ResolvedInserted.takeError();
+      auto Spelled = Includes.calculateIncludePath(*ResolvedInserted, FileName);
+      if (!Spelled)
+        return llvm::createStringError(llvm::inconvertibleErrorCode(),
+                                       "Header not on include path");
       return std::make_pair(
-          Includes.calculateIncludePath(*ResolvedInserted, FileName),
+          std::move(*Spelled),
           Includes.shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
     };
     bool ShouldInsert = C.headerToInsertIfAllowed(Opts).hasValue();
Index: clang-tools-extra/trunk/clangd/Headers.h
===================================================================
--- clang-tools-extra/trunk/clangd/Headers.h
+++ clang-tools-extra/trunk/clangd/Headers.h
@@ -171,15 +171,16 @@
   /// search path. Usually this will prefer a shorter representation like
   /// 'Foo/Bar.h' over a longer one like 'Baz/include/Foo/Bar.h'.
   ///
-  /// \param InsertedHeader The preferred header to be inserted. This could be
-  /// the same as DeclaringHeader but must be provided.
+  /// \param InsertedHeader The preferred header to be inserted.
   ///
   /// \param IncludingFile is the absolute path of the file that InsertedHeader
   /// will be inserted.
   ///
-  /// \return A quoted "path" or <path> to be included.
-  std::string calculateIncludePath(const HeaderFile &InsertedHeader,
-                                   llvm::StringRef IncludingFile) const;
+  /// \return A quoted "path" or <path> to be included, or None if it couldn't
+  /// be shortened.
+  llvm::Optional<std::string>
+  calculateIncludePath(const HeaderFile &InsertedHeader,
+                       llvm::StringRef IncludingFile) const;
 
   /// Calculates an edit that inserts \p VerbatimHeader into code. If the header
   /// is already included, this returns None.
Index: clang-tools-extra/trunk/clangd/Headers.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/Headers.cpp
+++ clang-tools-extra/trunk/clangd/Headers.cpp
@@ -186,19 +186,29 @@
   return !Included(DeclaringHeader) && !Included(InsertedHeader.File);
 }
 
-std::string
+llvm::Optional<std::string>
 IncludeInserter::calculateIncludePath(const HeaderFile &InsertedHeader,
                                       llvm::StringRef IncludingFile) const {
   assert(InsertedHeader.valid());
   if (InsertedHeader.Verbatim)
     return InsertedHeader.File;
   bool IsSystem = false;
-  // FIXME(kadircet): Handle same directory includes even if there is no
-  // HeaderSearchInfo.
-  if (!HeaderSearchInfo)
-    return "\"" + InsertedHeader.File + "\"";
-  std::string Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
-      InsertedHeader.File, BuildDir, IncludingFile, &IsSystem);
+  std::string Suggested;
+  if (HeaderSearchInfo) {
+    Suggested = HeaderSearchInfo->suggestPathToFileForDiagnostics(
+        InsertedHeader.File, BuildDir, IncludingFile, &IsSystem);
+  } else {
+    // Calculate include relative to including file only.
+    StringRef IncludingDir = llvm::sys::path::parent_path(IncludingFile);
+    SmallString<256> RelFile(InsertedHeader.File);
+    // Replacing with "" leaves "/RelFile" if IncludingDir doesn't end in "/".
+    llvm::sys::path::replace_path_prefix(RelFile, IncludingDir, "./");
+    Suggested = llvm::sys::path::convert_to_slash(
+        llvm::sys::path::remove_leading_dotslash(RelFile));
+  }
+  // FIXME: should we allow (some limited number of) "../header.h"?
+  if (llvm::sys::path::is_absolute(Suggested))
+    return None;
   if (IsSystem)
     Suggested = "<" + Suggested + ">";
   else
Index: clang-tools-extra/trunk/clangd/IncludeFixer.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/IncludeFixer.cpp
+++ clang-tools-extra/trunk/clangd/IncludeFixer.cpp
@@ -151,8 +151,12 @@
     auto ResolvedInserted = toHeaderFile(Header, File);
     if (!ResolvedInserted)
       return ResolvedInserted.takeError();
+    auto Spelled = Inserter->calculateIncludePath(*ResolvedInserted, File);
+    if (!Spelled)
+      return llvm::createStringError(llvm::inconvertibleErrorCode(),
+                                     "Header not on include path");
     return std::make_pair(
-        Inserter->calculateIncludePath(*ResolvedInserted, File),
+        std::move(*Spelled),
         Inserter->shouldInsertInclude(*ResolvedDeclaring, *ResolvedInserted));
   };
 
Index: clang-tools-extra/trunk/clangd/unittests/HeadersTests.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/unittests/HeadersTests.cpp
+++ clang-tools-extra/trunk/clangd/unittests/HeadersTests.cpp
@@ -97,9 +97,9 @@
     auto Inserted = ToHeaderFile(Preferred);
     if (!Inserter.shouldInsertInclude(Original, Inserted))
       return "";
-    std::string Path = Inserter.calculateIncludePath(Inserted, MainFile);
+    auto Path = Inserter.calculateIncludePath(Inserted, MainFile);
     Action.EndSourceFile();
-    return Path;
+    return Path.getValueOr("");
   }
 
   llvm::Optional<TextEdit> insert(llvm::StringRef VerbatimHeader) {
@@ -212,6 +212,11 @@
   EXPECT_EQ(calculate(MainFile), "");
 }
 
+TEST_F(HeadersTest, DoNotInsertOffIncludePath) {
+  MainFile = testPath("sub/main.cpp");
+  EXPECT_EQ(calculate(testPath("sub2/main.cpp")), "");
+}
+
 TEST_F(HeadersTest, ShortenIncludesInSearchPath) {
   std::string BarHeader = testPath("sub/bar.h");
   EXPECT_EQ(calculate(BarHeader), "\"bar.h\"");
@@ -268,13 +273,16 @@
   auto Inserting = HeaderFile{HeaderPath, /*Verbatim=*/false};
   auto Verbatim = HeaderFile{"<x>", /*Verbatim=*/true};
 
-  // FIXME(kadircet): This should result in "sub/bar.h" instead of full path.
   EXPECT_EQ(Inserter.calculateIncludePath(Inserting, MainFile),
-            '"' + HeaderPath + '"');
+            std::string("\"sub/bar.h\""));
   EXPECT_EQ(Inserter.shouldInsertInclude(HeaderPath, Inserting), false);
 
-  EXPECT_EQ(Inserter.calculateIncludePath(Verbatim, MainFile), "<x>");
+  EXPECT_EQ(Inserter.calculateIncludePath(Verbatim, MainFile),
+            std::string("<x>"));
   EXPECT_EQ(Inserter.shouldInsertInclude(HeaderPath, Verbatim), true);
+
+  EXPECT_EQ(Inserter.calculateIncludePath(Inserting, "sub2/main2.cpp"),
+            llvm::None);
 }
 
 } // namespace