Remove m_last_file_sp from SourceManager

[emrekultursay]

Summary

...and replace it with m_last_file_spec instead.

When Source Cache is enabled, the value stored in m_last_file_sp is
already in the Source Cache, and caching it again in SourceManager
brings no extra benefit. All we need is to "remember" the last used
file, and FileSpec can serve the same purpose.

When Source Cache is disabled, the user explicitly requested no caching
of source files, and therefore, m_last_file_sp should NOT be used.

Bug: llvm.org/PR45310

Depends on D76805.

[labath]

It's not clear to me what is the user-visible effect of this. It sounds like there should be one, but I don't know what it is...

lldb/source/Core/SourceManager.cpp

178–179

if(FileSP last_file_sp = GetLastFile())

255–256

Use GetLastFile, since we already have it.

269–270

same here

[emrekultursay]

In D76806#1943062, @labath wrote:

It's not clear to me what is the user-visible effect of this. It sounds like there should be one, but I don't know what it is...

If LLDB will cache FileSP shared pointers, there should be only one place for caching, and it's the Source File Cache, which can be enabled/disabled by the user.
User-facing effect of this change can be found in bug: llvm.org/PR45310

[emrekultursay]

Applied suggestions from labath@

[emrekultursay]

Added test that verifies end-to-end impact of
"setting set use_source_cache false" on Windows.

[emrekultursay]

Cleanup the Python test to make it a bit more readable

[emrekultursay]

PTAL.

[labath]

lldb/test/API/commands/settings/use_source_cache/TestUseSourceCache.py

18

Could you remove this decorator? The test is not extremely interesting on non-windows hosts, but the flow should still work, so there's no harm in testing it.

23

technically, this should be hostoslist=no_match(...)

31–71

All of this could be done via a single lldbutil.run_to_source_breakpoint call (that's a fairly new thing, so it's possible the test you based this on is not using it yet).

41

Please avoid modifying the source tree. You can take a look at test/API/source-manager/Makefile to see how to build binaries with sources in the build tree.

87–88

maybe:

if is_cache_enabled:
  self.assertFalse(is_file_removed)

(and similarly for the other case).

lldb/test/API/commands/settings/use_source_cache/header.h

1 ↗

(On Diff #253260)

Does this need to be in a separate file? Could you just put it into main.cpp ?

[emrekultursay]

PTAL. Applied suggested changes, thanks for the review!

[emrekultursay]

Fix formatting.

[labath]

I think this is fine now. Jim, do you have any more thoughts on this patchset?

lldb/test/API/commands/settings/use_source_cache/TestUseSourceCache.py

41

self.assertGreater

[emrekultursay]

use assertGreater instead of assertTrue(x>y)

[jingham]

There was one missing use of GetLastFile (as opposed to doing it by hand.)

Getting the default file is not used in any performance critical way that I'm aware of. It's mostly used for "break set -l" with no "-f" and list with no arguments and commands of that sort. So the extra lookup to get the FileSP from the source manager instead of caching it directly should not cause problems. And if you asked not to cache, you've already decided to pay the cost for that.

LGTM with that trivial fix.

lldb/source/Core/SourceManager.cpp

178–179

Doesn't look like this got converted to GetLastFile.

[emrekultursay]

Fix missing use of GetLastFile

[emrekultursay]

I don't have commit access, can someone with access commit all three approved CLs in this stack?

[labath]

I am afraid that the last patch in this series introduces a bunch of failures for me. The failures appear to be more-or-less consistent, but the impacted tests seem pretty random:

lldb-api :: commands/expression/persistent_ptr_update/TestPersistentPtrUpdate.py
lldb-api :: commands/expression/persistent_variables/TestPersistentVariables.py
lldb-api :: commands/watchpoints/hello_watchlocation/TestWatchLocation.py
lldb-api :: commands/watchpoints/hello_watchpoint/TestMyFirstWatchpoint.py
lldb-api :: commands/watchpoints/watchpoint_commands/TestWatchpointCommands.py
lldb-api :: commands/watchpoints/watchpoint_commands/command/TestWatchpointCommandLLDB.py
lldb-api :: commands/watchpoints/watchpoint_commands/command/TestWatchpointCommandPython.py
lldb-api :: commands/watchpoints/watchpoint_commands/condition/TestWatchpointConditionCmd.py
lldb-api :: commands/watchpoints/watchpoint_set_command/TestWatchLocationWithWatchSet.py
lldb-api :: functionalities/breakpoint/auto_continue/TestBreakpointAutoContinue.py
lldb-api :: functionalities/breakpoint/breakpoint_command/TestRegexpBreakCommand.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/atomic/TestLibCxxAtomic.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/function/TestLibCxxFunction.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/map/TestDataFormatterLibccMap.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/multimap/TestDataFormatterLibccMultiMap.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/optional/TestDataFormatterLibcxxOptional.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libcxx/unordered/TestDataFormatterUnordered.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libstdcpp/map/TestDataFormatterStdMap.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libstdcpp/smart_ptr/TestDataFormatterStdSmartPtr.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libstdcpp/tuple/TestDataFormatterStdTuple.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libstdcpp/unique_ptr/TestDataFormatterStdUniquePtr.py
lldb-api :: functionalities/data-formatter/data-formatter-stl/libstdcpp/vector/TestDataFormatterStdVector.py
lldb-api :: functionalities/plugins/python_os_plugin/TestPythonOSPlugin.py
lldb-api :: functionalities/signal/handle-abrt/TestHandleAbort.py
lldb-api :: functionalities/type_completion/TestTypeCompletion.py
lldb-api :: lang/c/register_variables/TestRegisterVariables.py
lldb-api :: lang/cpp/class_types/TestClassTypes.py
lldb-api :: python_api/sbvalue_persist/TestSBValuePersist.py
lldb-shell :: Driver/TestSingleQuote.test
lldb-shell :: Settings/TestFrameFormatMangling.test

Reverting the last patch makes the problem go away, but I am not sure the problem is really there. Given that this series exposes a bunch of previously completely unused code, it could be that the problem is completely elsewhere.

Anyway, this needs to be redone somehow.

[emrekultursay]

Fix broken tests.

[emrekultursay]

Thanks for noticing the test breakages Pavel. I fixed the bug, and verified that the tests you mentioned pass. PTAL.

[labath]

In D76806#1973035, @emrekultursay wrote:

Thanks for noticing the test breakages Pavel. I fixed the bug, and verified that the tests you mentioned pass. PTAL.

Everything looks fine now. Thanks for fixing that (it would be nice to mention what the bug was so one doesn't have to dig through the patch history to figure it out). I'm going to commit this shortly.

lldb/include/lldb/Core/SourceManager.h

public:
   // use the path remappings to find
   // source files that are not in their build locations.  With no target it
   // won't be able to do this.
   SourceManager(const lldb::DebuggerSP &debugger_sp);
   SourceManager(const lldb::TargetSP &target_sp);
 
   ~SourceManager();
 
-  FileSP GetLastFile() { return m_last_file_sp; }
+  FileSP GetLastFile() { return GetFile(m_last_file_spec); }
 
   size_t
   DisplaySourceLinesWithLineNumbers(const FileSpec &file, uint32_t line,
                                     uint32_t column, uint32_t context_before,
                                     uint32_t context_after,
                                     const char *current_line_cstr, Stream *s,
                                     const SymbolContextList *bp_locs = nullptr);
 
   // This variant uses the last file we visited.
   size_t DisplaySourceLinesWithLineNumbersUsingLastFile(
       uint32_t start_line, uint32_t count, uint32_t curr_line, uint32_t column,
       const char *current_line_cstr, Stream *s,
       const SymbolContextList *bp_locs = nullptr);
 
   size_t DisplayMoreWithLineNumbers(Stream *s, uint32_t count, bool reverse,
                                     const SymbolContextList *bp_locs = nullptr);
 
   bool SetDefaultFileAndLine(const FileSpec &file_spec, uint32_t line);
 
   bool GetDefaultFileAndLine(FileSpec &file_spec, uint32_t &line);
 
-  bool DefaultFileAndLineSet() { return (m_last_file_sp.get() != nullptr); }
+  bool DefaultFileAndLineSet() {
+    return (GetFile(m_last_file_spec).get() != nullptr);
+  }
 
   void FindLinesMatchingRegex(FileSpec &file_spec, RegularExpression &regex,
                               uint32_t start_line, uint32_t end_line,
                               std::vector<uint32_t> &match_lines);
 
   FileSP GetFile(const FileSpec &file_spec);
 
 protected:
-  FileSP m_last_file_sp;
+  FileSpec m_last_file_spec;
   uint32_t m_last_line;
   uint32_t m_last_count;
   bool m_default_set;
   lldb::TargetWP m_target_wp;
   lldb::DebuggerWP m_debugger_wp;
 
 private:
   DISALLOW_COPY_AND_ASSIGN(SourceManager);
 };
 
 bool operator==(const SourceManager::File &lhs, const SourceManager::File &rhs);
 
 } // namespace lldb_private
 
 #endif // LLDB_CORE_SOURCEMANAGER_H

lldb/source/Core/SourceManager.cpp

 
 using namespace lldb;
 using namespace lldb_private;
 
 static inline bool is_newline_char(char ch) { return ch == '\n' || ch == '\r'; }
 
 // SourceManager constructor
 SourceManager::SourceManager(const TargetSP &target_sp)
-    : m_last_file_sp(), m_last_line(0), m_last_count(0), m_default_set(false),
+    : m_last_line(0), m_last_count(0), m_default_set(false),
       m_target_wp(target_sp),
       m_debugger_wp(target_sp->GetDebugger().shared_from_this()) {}
 
 SourceManager::SourceManager(const DebuggerSP &debugger_sp)
-    : m_last_file_sp(), m_last_line(0), m_last_count(0), m_default_set(false),
-      m_target_wp(), m_debugger_wp(debugger_sp) {}
+    : m_last_line(0), m_last_count(0), m_default_set(false), m_target_wp(),
+      m_debugger_wp(debugger_sp) {}
 
 // Destructor
 SourceManager::~SourceManager() {}
 
 SourceManager::FileSP SourceManager::GetFile(const FileSpec &file_spec) {
-  bool same_as_previous =
-      m_last_file_sp &&
-      FileSpec::Match(file_spec, m_last_file_sp->GetFileSpec());
+  if (!file_spec)
+    return nullptr;
 
   DebuggerSP debugger_sp(m_debugger_wp.lock());
   FileSP file_sp;
-  if (same_as_previous)
-    file_sp = m_last_file_sp;
-  else if (debugger_sp && debugger_sp->GetUseSourceCache())
+  if (debugger_sp && debugger_sp->GetUseSourceCache())
     file_sp = debugger_sp->GetSourceFileCache().FindSourceFile(file_spec);
 
   TargetSP target_sp(m_target_wp.lock());
 
   // It the target source path map has been updated, get this file again so we
   // can successfully remap the source file
   if (target_sp && file_sp &&
       file_sp->GetSourceMapModificationID() !=
if (!m_default_set) {
     FileSpec tmp_spec;
     uint32_t tmp_line;
     GetDefaultFileAndLine(tmp_spec, tmp_line);
   }
 
   m_last_line = start_line;
   m_last_count = count;
 
-  if (m_last_file_sp.get()) {
+  if (FileSP last_file_sp = GetLastFile()) {
     const uint32_t end_line = start_line + count - 1;
     for (uint32_t line = start_line; line <= end_line; ++line) {
-      if (!m_last_file_sp->LineIsValid(line)) {
+      if (!last_file_sp->LineIsValid(line)) {
         m_last_line = UINT32_MAX;
         break;
       }
 
       char prefix[32] = "";
       if (bp_locs) {
         uint32_t bp_count = bp_locs->NumLineEntriesWithLine(line);
 
for (uint32_t line = start_line; line <= end_line; ++line) {
       // So far we treated column 0 as a special 'no column value', but
       // DisplaySourceLines starts counting columns from 0 (and no column is
       // expressed by passing an empty optional).
       llvm::Optional<size_t> columnToHighlight;
       if (line == curr_line && column)
         columnToHighlight = column - 1;
 
       size_t this_line_size =
-          m_last_file_sp->DisplaySourceLines(line, columnToHighlight, 0, 0, s);
+          last_file_sp->DisplaySourceLines(line, columnToHighlight, 0, 0, s);
       if (column != 0 && line == curr_line &&
           should_show_stop_column_with_caret(debugger_sp)) {
         // Display caret cursor.
         std::string src_line;
-        m_last_file_sp->GetLine(line, src_line);
+        last_file_sp->GetLine(line, src_line);
         s->Printf("    \t");
         // Insert a space for every non-tab character in the source line.
         for (size_t i = 0; i + 1 < column && i < src_line.length(); ++i)
           s->PutChar(src_line[i] == '\t' ? '\t' : ' ');
         // Now add the caret.
         s->Printf("^\n");
       }
       if (this_line_size == 0) {
size_t SourceManager::DisplaySourceLinesWithLineNumbers(
 
   uint32_t start_line;
   uint32_t count = context_before + context_after + 1;
   if (line > context_before)
     start_line = line - context_before;
   else
     start_line = 1;
 
-  if (m_last_file_sp.get() != file_sp.get()) {
+  FileSP last_file_sp(GetLastFile());
+  if (last_file_sp.get() != file_sp.get()) {
     if (line == 0)
       m_last_line = 0;
-    m_last_file_sp = file_sp;
+    m_last_file_spec = file_spec;
   }
   return DisplaySourceLinesWithLineNumbersUsingLastFile(
       start_line, count, line, column, current_line_cstr, s, bp_locs);
 }
 
 size_t SourceManager::DisplayMoreWithLineNumbers(
     Stream *s, uint32_t count, bool reverse, const SymbolContextList *bp_locs) {
   // If we get called before anybody has set a default file and line, then try
   // to figure it out here.
-  const bool have_default_file_line = m_last_file_sp && m_last_line > 0;
+  FileSP last_file_sp(GetLastFile());
+  const bool have_default_file_line = last_file_sp && m_last_line > 0;
   if (!m_default_set) {
     FileSpec tmp_spec;
     uint32_t tmp_line;
     GetDefaultFileAndLine(tmp_spec, tmp_line);
   }
 
-  if (m_last_file_sp) {
+  if (last_file_sp) {
     if (m_last_line == UINT32_MAX)
       return 0;
 
     if (reverse && m_last_line == 1)
       return 0;
 
     if (count > 0)
       m_last_count = count;
if (last_file_sp) {
     return DisplaySourceLinesWithLineNumbersUsingLastFile(
         m_last_line, m_last_count, UINT32_MAX, column, "", s, bp_locs);
   }
   return 0;
 }
 
 bool SourceManager::SetDefaultFileAndLine(const FileSpec &file_spec,
                                           uint32_t line) {
-  FileSP old_file_sp = m_last_file_sp;
-  m_last_file_sp = GetFile(file_spec);
-
   m_default_set = true;
-  if (m_last_file_sp) {
+  FileSP file_sp(GetFile(file_spec));
+
+  if (file_sp) {
     m_last_line = line;
+    m_last_file_spec = file_spec;
     return true;
   } else {
-    m_last_file_sp = old_file_sp;
     return false;
   }
 }
 
 bool SourceManager::GetDefaultFileAndLine(FileSpec &file_spec, uint32_t &line) {
-  if (m_last_file_sp) {
-    file_spec = m_last_file_sp->GetFileSpec();
+  if (FileSP last_file_sp = GetLastFile()) {
+    file_spec = m_last_file_spec;
     line = m_last_line;
     return true;
   } else if (!m_default_set) {
     TargetSP target_sp(m_target_wp.lock());
 
     if (target_sp) {
       // If nobody has set the default file and line then try here.  If there's
       // no executable, then we will try again later when there is one.
if (target_sp) {
           SymbolContext sc;
           sc_list.GetContextAtIndex(idx, sc);
           if (sc.function) {
             lldb_private::LineEntry line_entry;
             if (sc.function->GetAddressRange()
                     .GetBaseAddress()
                     .CalculateSymbolContextLineEntry(line_entry)) {
               SetDefaultFileAndLine(line_entry.file, line_entry.line);
-              file_spec = m_last_file_sp->GetFileSpec();
+              file_spec = m_last_file_spec;
               line = m_last_line;
               return true;
             }
           }
         }
       }
     }
   }

lldb/test/API/commands/settings/use_source_cache/Makefile

+CXX_SOURCES := main-copy.cpp
+
+include Makefile.rules
+
+
+# Copy file into the build folder to enable the test to modify it.
+main-copy.cpp: main.cpp
+  cp -f $< $@

lldb/test/API/commands/settings/use_source_cache/TestUseSourceCache.py

+"""
+Tests large source files are not locked on Windows when source cache is disabled
+"""
+
+import lldb
+import os
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+from shutil import copy
+
+class SettingsUseSourceCacheTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+    NO_DEBUG_INFO_TESTCASE = True
+
+    def test_set_use_source_cache_false(self):
+        """Test that after 'set use-source-cache false', files are not locked."""
+        self.set_use_source_cache_and_test(False)
+
+    @skipIf(hostoslist=no_match(["windows"]))
+    def test_set_use_source_cache_true(self):
+        """Test that after 'set use-source-cache false', files are locked."""
+        self.set_use_source_cache_and_test(True)
+
+    def set_use_source_cache_and_test(self, is_cache_enabled):
+        """Common test for both True/False values of use-source-cache."""
+        self.build()
+
+        # Enable/Disable source cache
+        self.runCmd(
+                "settings set use-source-cache " +
+                ("true" if is_cache_enabled else "false"))
+
+        # Get paths for the main source file.
+        src = self.getBuildArtifact("main-copy.cpp")
+        self.assertTrue(src)
+
+        # Make sure source file is bigger than 16K to trigger memory mapping
+        self.assertGreater(os.stat(src).st_size, 4*4096)
+
+        target, process, thread, breakpoint = lldbutil.run_to_name_breakpoint(
+                self,
+                "calc")
+
+        # Show the source file contents to make sure LLDB loads src file.
+        self.runCmd("source list")
+
+        # Try deleting the source file.
+        is_file_removed = self.removeFile(src)
+
+        if is_cache_enabled:
+            self.assertFalse(
+                is_file_removed,
+                "Source cache is enabled, but delete file succeeded")
+        
+        if not is_cache_enabled:
+            self.assertTrue(
+                is_file_removed,
+                "Source cache is disabled, but delete file failed")
+
+    def removeFile(self, src):
+        """Remove file and return true iff file was successfully removed."""
+        try:
+            os.remove(src)
+            return True
+        except Exception:
+            return False
+

lldb/test/API/commands/settings/use_source_cache/main.cpp

+// This file should be large enough that LLDB decides to load it
+// using memory mapping. See:
+//   ⁠llvm/lib/Support/MemoryBuffer.cp:shouldUseMmap()
+
+#include <stdio.h>
+
+int calc(int x0, int x1, int x2);
+
+int main(int argc, char const *argv[]) {
+  fprintf(stderr, "Hello, world => %d\n", calc(0, 1, 2));
+  return 0;
+}
+
+// The name of this function is used in tests to set breakpoints by name.
+int calc(int x0, int x1, int x2) {
+  int x3 = x2 * x1 + x0;
+  int x4 = x3 * x2 + x1;
+  int x5 = x4 * x3 + x2;
+  int x6 = x5 * x4 + x3;
+  int x7 = x6 * x5 + x4;
+  int x8 = x7 * x6 + x5;
+  int x9 = x8 * x7 + x6;
+  int x10 = x9 * x8 + x7;
+  int x11 = x10 * x9 + x8;
+  int x12 = x11 * x10 + x9;
+  int x13 = x12 * x11 + x10;
+  int x14 = x13 * x12 + x11;
+  int x15 = x14 * x13 + x12;
+  int x16 = x15 * x14 + x13;
+  int x17 = x16 * x15 + x14;
+  int x18 = x17 * x16 + x15;
+  int x19 = x18 * x17 + x16;
+  int x20 = x19 * x18 + x17;
+  int x21 = x20 * x19 + x18;
+  int x22 = x21 * x20 + x19;
+  int x23 = x22 * x21 + x20;
+  int x24 = x23 * x22 + x21;
+  int x25 = x24 * x23 + x22;
+  int x26 = x25 * x24 + x23;
+  int x27 = x26 * x25 + x24;
+  int x28 = x27 * x26 + x25;
+  int x29 = x28 * x27 + x26;
+  int x30 = x29 * x28 + x27;
+  int x31 = x30 * x29 + x28;
+  int x32 = x31 * x30 + x29;
+  int x33 = x32 * x31 + x30;
+  int x34 = x33 * x32 + x31;
+  int x35 = x34 * x33 + x32;
+  int x36 = x35 * x34 + x33;
+  int x37 = x36 * x35 + x34;
+  int x38 = x37 * x36 + x35;
+  int x39 = x38 * x37 + x36;
+  int x40 = x39 * x38 + x37;
+  int x41 = x40 * x39 + x38;
+  int x42 = x41 * x40 + x39;
+  int x43 = x42 * x41 + x40;
+  int x44 = x43 * x42 + x41;
+  int x45 = x44 * x43 + x42;
+  int x46 = x45 * x44 + x43;
+  int x47 = x46 * x45 + x44;
+  int x48 = x47 * x46 + x45;
+  int x49 = x48 * x47 + x46;
+  int x50 = x49 * x48 + x47;
+  int x51 = x50 * x49 + x48;
+  int x52 = x51 * x50 + x49;
+  int x53 = x52 * x51 + x50;
+  int x54 = x53 * x52 + x51;
+  int x55 = x54 * x53 + x52;
+  int x56 = x55 * x54 + x53;
+  int x57 = x56 * x55 + x54;
+  int x58 = x57 * x56 + x55;
+  int x59 = x58 * x57 + x56;
+  int x60 = x59 * x58 + x57;
+  int x61 = x60 * x59 + x58;
+  int x62 = x61 * x60 + x59;
+  int x63 = x62 * x61 + x60;
+  int x64 = x63 * x62 + x61;
+  int x65 = x64 * x63 + x62;
+  int x66 = x65 * x64 + x63;
+  int x67 = x66 * x65 + x64;
+  int x68 = x67 * x66 + x65;
+  int x69 = x68 * x67 + x66;
+  int x70 = x69 * x68 + x67;
+  int x71 = x70 * x69 + x68;
+  int x72 = x71 * x70 + x69;
+  int x73 = x72 * x71 + x70;
+  int x74 = x73 * x72 + x71;
+  int x75 = x74 * x73 + x72;
+  int x76 = x75 * x74 + x73;
+  int x77 = x76 * x75 + x74;
+  int x78 = x77 * x76 + x75;
+  int x79 = x78 * x77 + x76;
+  int x80 = x79 * x78 + x77;
+  int x81 = x80 * x79 + x78;
+  int x82 = x81 * x80 + x79;
+  int x83 = x82 * x81 + x80;
+  int x84 = x83 * x82 + x81;
+  int x85 = x84 * x83 + x82;
+  int x86 = x85 * x84 + x83;
+  int x87 = x86 * x85 + x84;
+  int x88 = x87 * x86 + x85;
+  int x89 = x88 * x87 + x86;
+  int x90 = x89 * x88 + x87;
+  int x91 = x90 * x89 + x88;
+  int x92 = x91 * x90 + x89;
+  int x93 = x92 * x91 + x90;
+  int x94 = x93 * x92 + x91;
+  int x95 = x94 * x93 + x92;
+  int x96 = x95 * x94 + x93;
+  int x97 = x96 * x95 + x94;
+  int x98 = x97 * x96 + x95;
+  int x99 = x98 * x97 + x96;
+  int x100 = x99 * x98 + x97;
+  int x101 = x100 * x99 + x98;
+  int x102 = x101 * x100 + x99;
+  int x103 = x102 * x101 + x100;
+  int x104 = x103 * x102 + x101;
+  int x105 = x104 * x103 + x102;
+  int x106 = x105 * x104 + x103;
+  int x107 = x106 * x105 + x104;
+  int x108 = x107 * x106 + x105;
+  int x109 = x108 * x107 + x106;
+  int x110 = x109 * x108 + x107;
+  int x111 = x110 * x109 + x108;
+  int x112 = x111 * x110 + x109;
+  int x113 = x112 * x111 + x110;
+  int x114 = x113 * x112 + x111;
+  int x115 = x114 * x113 + x112;
+  int x116 = x115 * x114 + x113;
+  int x117 = x116 * x115 + x114;
+  int x118 = x117 * x116 + x115;
+  int x119 = x118 * x117 + x116;
+  int x120 = x119 * x118 + x117;
+  int x121 = x120 * x119 + x118;
+  int x122 = x121 * x120 + x119;
+  int x123 = x122 * x121 + x120;
+  int x124 = x123 * x122 + x121;
+  int x125 = x124 * x123 + x122;
+  int x126 = x125 * x124 + x123;
+  int x127 = x126 * x125 + x124;
+  int x128 = x127 * x126 + x125;
+  int x129 = x128 * x127 + x126;
+  int x130 = x129 * x128 + x127;
+  int x131 = x130 * x129 + x128;
+  int x132 = x131 * x130 + x129;
+  int x133 = x132 * x131 + x130;
+  int x134 = x133 * x132 + x131;
+  int x135 = x134 * x133 + x132;
+  int x136 = x135 * x134 + x133;
+  int x137 = x136 * x135 + x134;
+  int x138 = x137 * x136 + x135;
+  int x139 = x138 * x137 + x136;
+  int x140 = x139 * x138 + x137;
+  int x141 = x140 * x139 + x138;
+  int x142 = x141 * x140 + x139;
+  int x143 = x142 * x141 + x140;
+  int x144 = x143 * x142 + x141;
+  int x145 = x144 * x143 + x142;
+  int x146 = x145 * x144 + x143;
+  int x147 = x146 * x145 + x144;
+  int x148 = x147 * x146 + x145;
+  int x149 = x148 * x147 + x146;
+  int x150 = x149 * x148 + x147;
+  int x151 = x150 * x149 + x148;
+  int x152 = x151 * x150 + x149;
+  int x153 = x152 * x151 + x150;
+  int x154 = x153 * x152 + x151;
+  int x155 = x154 * x153 + x152;
+  int x156 = x155 * x154 + x153;
+  int x157 = x156 * x155 + x154;
+  int x158 = x157 * x156 + x155;
+  int x159 = x158 * x157 + x156;
+  int x160 = x159 * x158 + x157;
+  int x161 = x160 * x159 + x158;
+  int x162 = x161 * x160 + x159;
+  int x163 = x162 * x161 + x160;
+  int x164 = x163 * x162 + x161;
+  int x165 = x164 * x163 + x162;
+  int x166 = x165 * x164 + x163;
+  int x167 = x166 * x165 + x164;
+  int x168 = x167 * x166 + x165;
+  int x169 = x168 * x167 + x166;
+  int x170 = x169 * x168 + x167;
+  int x171 = x170 * x169 + x168;
+  int x172 = x171 * x170 + x169;
+  int x173 = x172 * x171 + x170;
+  int x174 = x173 * x172 + x171;
+  int x175 = x174 * x173 + x172;
+  int x176 = x175 * x174 + x173;
+  int x177 = x176 * x175 + x174;
+  int x178 = x177 * x176 + x175;
+  int x179 = x178 * x177 + x176;
+  int x180 = x179 * x178 + x177;
+  int x181 = x180 * x179 + x178;
+  int x182 = x181 * x180 + x179;
+  int x183 = x182 * x181 + x180;
+  int x184 = x183 * x182 + x181;
+  int x185 = x184 * x183 + x182;
+  int x186 = x185 * x184 + x183;
+  int x187 = x186 * x185 + x184;
+  int x188 = x187 * x186 + x185;
+  int x189 = x188 * x187 + x186;
+  int x190 = x189 * x188 + x187;
+  int x191 = x190 * x189 + x188;
+  int x192 = x191 * x190 + x189;
+  int x193 = x192 * x191 + x190;
+  int x194 = x193 * x192 + x191;
+  int x195 = x194 * x193 + x192;
+  int x196 = x195 * x194 + x193;
+  int x197 = x196 * x195 + x194;
+  int x198 = x197 * x196 + x195;
+  int x199 = x198 * x197 + x196;
+  int x200 = x199 * x198 + x197;
+  int x201 = x200 * x199 + x198;
+  int x202 = x201 * x200 + x199;
+  int x203 = x202 * x201 + x200;
+  int x204 = x203 * x202 + x201;
+  int x205 = x204 * x203 + x202;
+  int x206 = x205 * x204 + x203;
+  int x207 = x206 * x205 + x204;
+  int x208 = x207 * x206 + x205;
+  int x209 = x208 * x207 + x206;
+  int x210 = x209 * x208 + x207;
+  int x211 = x210 * x209 + x208;
+  int x212 = x211 * x210 + x209;
+  int x213 = x212 * x211 + x210;
+  int x214 = x213 * x212 + x211;
+  int x215 = x214 * x213 + x212;
+  int x216 = x215 * x214 + x213;
+  int x217 = x216 * x215 + x214;
+  int x218 = x217 * x216 + x215;
+  int x219 = x218 * x217 + x216;
+  int x220 = x219 * x218 + x217;
+  int x221 = x220 * x219 + x218;
+  int x222 = x221 * x220 + x219;
+  int x223 = x222 * x221 + x220;
+  int x224 = x223 * x222 + x221;
+  int x225 = x224 * x223 + x222;
+  int x226 = x225 * x224 + x223;
+  int x227 = x226 * x225 + x224;
+  int x228 = x227 * x226 + x225;
+  int x229 = x228 * x227 + x226;
+  int x230 = x229 * x228 + x227;
+  int x231 = x230 * x229 + x228;
+  int x232 = x231 * x230 + x229;
+  int x233 = x232 * x231 + x230;
+  int x234 = x233 * x232 + x231;
+  int x235 = x234 * x233 + x232;
+  int x236 = x235 * x234 + x233;
+  int x237 = x236 * x235 + x234;
+  int x238 = x237 * x236 + x235;
+  int x239 = x238 * x237 + x236;
+  int x240 = x239 * x238 + x237;
+  int x241 = x240 * x239 + x238;
+  int x242 = x241 * x240 + x239;
+  int x243 = x242 * x241 + x240;
+  int x244 = x243 * x242 + x241;
+  int x245 = x244 * x243 + x242;
+  int x246 = x245 * x244 + x243;
+  int x247 = x246 * x245 + x244;
+  int x248 = x247 * x246 + x245;
+  int x249 = x248 * x247 + x246;
+  int x250 = x249 * x248 + x247;
+  int x251 = x250 * x249 + x248;
+  int x252 = x251 * x250 + x249;
+  int x253 = x252 * x251 + x250;
+  int x254 = x253 * x252 + x251;
+  int x255 = x254 * x253 + x252;
+  int x256 = x255 * x254 + x253;
+  int x257 = x256 * x255 + x254;
+  int x258 = x257 * x256 + x255;
+  int x259 = x258 * x257 + x256;
+  int x260 = x259 * x258 + x257;
+  int x261 = x260 * x259 + x258;
+  int x262 = x261 * x260 + x259;
+  int x263 = x262 * x261 + x260;
+  int x264 = x263 * x262 + x261;
+  int x265 = x264 * x263 + x262;
+  int x266 = x265 * x264 + x263;
+  int x267 = x266 * x265 + x264;
+  int x268 = x267 * x266 + x265;
+  int x269 = x268 * x267 + x266;
+  int x270 = x269 * x268 + x267;
+  int x271 = x270 * x269 + x268;
+  int x272 = x271 * x270 + x269;
+  int x273 = x272 * x271 + x270;
+  int x274 = x273 * x272 + x271;
+  int x275 = x274 * x273 + x272;
+  int x276 = x275 * x274 + x273;
+  int x277 = x276 * x275 + x274;
+  int x278 = x277 * x276 + x275;
+  int x279 = x278 * x277 + x276;
+  int x280 = x279 * x278 + x277;
+  int x281 = x280 * x279 + x278;
+  int x282 = x281 * x280 + x279;
+  int x283 = x282 * x281 + x280;
+  int x284 = x283 * x282 + x281;
+  int x285 = x284 * x283 + x282;
+  int x286 = x285 * x284 + x283;
+  int x287 = x286 * x285 + x284;
+  int x288 = x287 * x286 + x285;
+  int x289 = x288 * x287 + x286;
+  int x290 = x289 * x288 + x287;
+  int x291 = x290 * x289 + x288;
+  int x292 = x291 * x290 + x289;
+  int x293 = x292 * x291 + x290;
+  int x294 = x293 * x292 + x291;
+  int x295 = x294 * x293 + x292;
+  int x296 = x295 * x294 + x293;
+  int x297 = x296 * x295 + x294;
+  int x298 = x297 * x296 + x295;
+  int x299 = x298 * x297 + x296;
+  int x300 = x299 * x298 + x297;
+  int x301 = x300 * x299 + x298;
+  int x302 = x301 * x300 + x299;
+  int x303 = x302 * x301 + x300;
+  int x304 = x303 * x302 + x301;
+  int x305 = x304 * x303 + x302;
+  int x306 = x305 * x304 + x303;
+  int x307 = x306 * x305 + x304;
+  int x308 = x307 * x306 + x305;
+  int x309 = x308 * x307 + x306;
+  int x310 = x309 * x308 + x307;
+  int x311 = x310 * x309 + x308;
+  int x312 = x311 * x310 + x309;
+  int x313 = x312 * x311 + x310;
+  int x314 = x313 * x312 + x311;
+  int x315 = x314 * x313 + x312;
+  int x316 = x315 * x314 + x313;
+  int x317 = x316 * x315 + x314;
+  int x318 = x317 * x316 + x315;
+  int x319 = x318 * x317 + x316;
+  int x320 = x319 * x318 + x317;
+  int x321 = x320 * x319 + x318;
+  int x322 = x321 * x320 + x319;
+  int x323 = x322 * x321 + x320;
+  int x324 = x323 * x322 + x321;
+  int x325 = x324 * x323 + x322;
+  int x326 = x325 * x324 + x323;
+  int x327 = x326 * x325 + x324;
+  int x328 = x327 * x326 + x325;
+  int x329 = x328 * x327 + x326;
+  int x330 = x329 * x328 + x327;
+  int x331 = x330 * x329 + x328;
+  int x332 = x331 * x330 + x329;
+  int x333 = x332 * x331 + x330;
+  int x334 = x333 * x332 + x331;
+  int x335 = x334 * x333 + x332;
+  int x336 = x335 * x334 + x333;
+  int x337 = x336 * x335 + x334;
+  int x338 = x337 * x336 + x335;
+  int x339 = x338 * x337 + x336;
+  int x340 = x339 * x338 + x337;
+  int x341 = x340 * x339 + x338;
+  int x342 = x341 * x340 + x339;
+  int x343 = x342 * x341 + x340;
+  int x344 = x343 * x342 + x341;
+  int x345 = x344 * x343 + x342;
+  int x346 = x345 * x344 + x343;
+  int x347 = x346 * x345 + x344;
+  int x348 = x347 * x346 + x345;
+  int x349 = x348 * x347 + x346;
+  int x350 = x349 * x348 + x347;
+  int x351 = x350 * x349 + x348;
+  int x352 = x351 * x350 + x349;
+  int x353 = x352 * x351 + x350;
+  int x354 = x353 * x352 + x351;
+  int x355 = x354 * x353 + x352;
+  int x356 = x355 * x354 + x353;
+  int x357 = x356 * x355 + x354;
+  int x358 = x357 * x356 + x355;
+  int x359 = x358 * x357 + x356;
+  int x360 = x359 * x358 + x357;
+  int x361 = x360 * x359 + x358;
+  int x362 = x361 * x360 + x359;
+  int x363 = x362 * x361 + x360;
+  int x364 = x363 * x362 + x361;
+  int x365 = x364 * x363 + x362;
+  int x366 = x365 * x364 + x363;
+  int x367 = x366 * x365 + x364;
+  int x368 = x367 * x366 + x365;
+  int x369 = x368 * x367 + x366;
+  int x370 = x369 * x368 + x367;
+  int x371 = x370 * x369 + x368;
+  int x372 = x371 * x370 + x369;
+  int x373 = x372 * x371 + x370;
+  int x374 = x373 * x372 + x371;
+  int x375 = x374 * x373 + x372;
+  int x376 = x375 * x374 + x373;
+  int x377 = x376 * x375 + x374;
+  int x378 = x377 * x376 + x375;
+  int x379 = x378 * x377 + x376;
+  int x380 = x379 * x378 + x377;
+  int x381 = x380 * x379 + x378;
+  int x382 = x381 * x380 + x379;
+  int x383 = x382 * x381 + x380;
+  int x384 = x383 * x382 + x381;
+  int x385 = x384 * x383 + x382;
+  int x386 = x385 * x384 + x383;
+  int x387 = x386 * x385 + x384;
+  int x388 = x387 * x386 + x385;
+  int x389 = x388 * x387 + x386;
+  int x390 = x389 * x388 + x387;
+  int x391 = x390 * x389 + x388;
+  int x392 = x391 * x390 + x389;
+  int x393 = x392 * x391 + x390;
+  int x394 = x393 * x392 + x391;
+  int x395 = x394 * x393 + x392;
+  int x396 = x395 * x394 + x393;
+  int x397 = x396 * x395 + x394;
+  int x398 = x397 * x396 + x395;
+  int x399 = x398 * x397 + x396;
+  int x400 = x399 * x398 + x397;
+  int x401 = x400 * x399 + x398;
+  int x402 = x401 * x400 + x399;
+  int x403 = x402 * x401 + x400;
+  int x404 = x403 * x402 + x401;
+  int x405 = x404 * x403 + x402;
+  int x406 = x405 * x404 + x403;
+  int x407 = x406 * x405 + x404;
+  int x408 = x407 * x406 + x405;
+  int x409 = x408 * x407 + x406;
+  int x410 = x409 * x408 + x407;
+  int x411 = x410 * x409 + x408;
+  int x412 = x411 * x410 + x409;
+  int x413 = x412 * x411 + x410;
+  int x414 = x413 * x412 + x411;
+  int x415 = x414 * x413 + x412;
+  int x416 = x415 * x414 + x413;
+  int x417 = x416 * x415 + x414;
+  int x418 = x417 * x416 + x415;
+  int x419 = x418 * x417 + x416;
+  int x420 = x419 * x418 + x417;
+  int x421 = x420 * x419 + x418;
+  int x422 = x421 * x420 + x419;
+  int x423 = x422 * x421 + x420;
+  int x424 = x423 * x422 + x421;
+  int x425 = x424 * x423 + x422;
+  int x426 = x425 * x424 + x423;
+  int x427 = x426 * x425 + x424;
+  int x428 = x427 * x426 + x425;
+  int x429 = x428 * x427 + x426;
+  int x430 = x429 * x428 + x427;
+  int x431 = x430 * x429 + x428;
+  int x432 = x431 * x430 + x429;
+  int x433 = x432 * x431 + x430;
+  int x434 = x433 * x432 + x431;
+  int x435 = x434 * x433 + x432;
+  int x436 = x435 * x434 + x433;
+  int x437 = x436 * x435 + x434;
+  int x438 = x437 * x436 + x435;
+  int x439 = x438 * x437 + x436;
+  int x440 = x439 * x438 + x437;
+  int x441 = x440 * x439 + x438;
+  int x442 = x441 * x440 + x439;
+  int x443 = x442 * x441 + x440;
+  int x444 = x443 * x442 + x441;
+  int x445 = x444 * x443 + x442;
+  int x446 = x445 * x444 + x443;
+  int x447 = x446 * x445 + x444;
+  int x448 = x447 * x446 + x445;
+  int x449 = x448 * x447 + x446;
+  int x450 = x449 * x448 + x447;
+  int x451 = x450 * x449 + x448;
+  int x452 = x451 * x450 + x449;
+  int x453 = x452 * x451 + x450;
+  int x454 = x453 * x452 + x451;
+  int x455 = x454 * x453 + x452;
+  int x456 = x455 * x454 + x453;
+  int x457 = x456 * x455 + x454;
+  int x458 = x457 * x456 + x455;
+  int x459 = x458 * x457 + x456;
+  int x460 = x459 * x458 + x457;
+  int x461 = x460 * x459 + x458;
+  int x462 = x461 * x460 + x459;
+  int x463 = x462 * x461 + x460;
+  int x464 = x463 * x462 + x461;
+  int x465 = x464 * x463 + x462;
+  int x466 = x465 * x464 + x463;
+  int x467 = x466 * x465 + x464;
+  int x468 = x467 * x466 + x465;
+  int x469 = x468 * x467 + x466;
+  int x470 = x469 * x468 + x467;
+  int x471 = x470 * x469 + x468;
+  int x472 = x471 * x470 + x469;
+  int x473 = x472 * x471 + x470;
+  int x474 = x473 * x472 + x471;
+  int x475 = x474 * x473 + x472;
+  int x476 = x475 * x474 + x473;
+  int x477 = x476 * x475 + x474;
+  int x478 = x477 * x476 + x475;
+  int x479 = x478 * x477 + x476;
+  int x480 = x479 * x478 + x477;
+  int x481 = x480 * x479 + x478;
+  int x482 = x481 * x480 + x479;
+  int x483 = x482 * x481 + x480;
+  int x484 = x483 * x482 + x481;
+  int x485 = x484 * x483 + x482;
+  int x486 = x485 * x484 + x483;
+  int x487 = x486 * x485 + x484;
+  int x488 = x487 * x486 + x485;
+  int x489 = x488 * x487 + x486;
+  int x490 = x489 * x488 + x487;
+  int x491 = x490 * x489 + x488;
+  int x492 = x491 * x490 + x489;
+  int x493 = x492 * x491 + x490;
+  int x494 = x493 * x492 + x491;
+  int x495 = x494 * x493 + x492;
+  int x496 = x495 * x494 + x493;
+  int x497 = x496 * x495 + x494;
+  int x498 = x497 * x496 + x495;
+  int x499 = x498 * x497 + x496;
+  int x500 = x499 * x498 + x497;
+  int x501 = x500 * x499 + x498;
+  int x502 = x501 * x500 + x499;
+  int x503 = x502 * x501 + x500;
+  int x504 = x503 * x502 + x501;
+  int x505 = x504 * x503 + x502;
+  int x506 = x505 * x504 + x503;
+  int x507 = x506 * x505 + x504;
+  int x508 = x507 * x506 + x505;
+  int x509 = x508 * x507 + x506;
+  int x510 = x509 * x508 + x507;
+  int x511 = x510 * x509 + x508;
+  int x512 = x511 * x510 + x509;
+  int x513 = x512 * x511 + x510;
+  int x514 = x513 * x512 + x511;
+  int x515 = x514 * x513 + x512;
+  int x516 = x515 * x514 + x513;
+  int x517 = x516 * x515 + x514;
+  int x518 = x517 * x516 + x515;
+  int x519 = x518 * x517 + x516;
+  int x520 = x519 * x518 + x517;
+  int x521 = x520 * x519 + x518;
+  int x522 = x521 * x520 + x519;
+  int x523 = x522 * x521 + x520;
+  int x524 = x523 * x522 + x521;
+  int x525 = x524 * x523 + x522;
+  int x526 = x525 * x524 + x523;
+  int x527 = x526 * x525 + x524;
+  int x528 = x527 * x526 + x525;
+  int x529 = x528 * x527 + x526;
+  int x530 = x529 * x528 + x527;
+  int x531 = x530 * x529 + x528;
+  int x532 = x531 * x530 + x529;
+  int x533 = x532 * x531 + x530;
+  int x534 = x533 * x532 + x531;
+  int x535 = x534 * x533 + x532;
+  int x536 = x535 * x534 + x533;
+  int x537 = x536 * x535 + x534;
+  int x538 = x537 * x536 + x535;
+  int x539 = x538 * x537 + x536;
+  int x540 = x539 * x538 + x537;
+  int x541 = x540 * x539 + x538;
+  int x542 = x541 * x540 + x539;
+  int x543 = x542 * x541 + x540;
+  int x544 = x543 * x542 + x541;
+  int x545 = x544 * x543 + x542;
+  int x546 = x545 * x544 + x543;
+  int x547 = x546 * x545 + x544;
+  int x548 = x547 * x546 + x545;
+  int x549 = x548 * x547 + x546;
+  int x550 = x549 * x548 + x547;
+  int x551 = x550 * x549 + x548;
+  int x552 = x551 * x550 + x549;
+  int x553 = x552 * x551 + x550;
+  int x554 = x553 * x552 + x551;
+  int x555 = x554 * x553 + x552;
+  int x556 = x555 * x554 + x553;
+  int x557 = x556 * x555 + x554;
+  int x558 = x557 * x556 + x555;
+  int x559 = x558 * x557 + x556;
+  int x560 = x559 * x558 + x557;
+  int x561 = x560 * x559 + x558;
+  int x562 = x561 * x560 + x559;
+  int x563 = x562 * x561 + x560;
+  int x564 = x563 * x562 + x561;
+  int x565 = x564 * x563 + x562;
+  int x566 = x565 * x564 + x563;
+  int x567 = x566 * x565 + x564;
+  int x568 = x567 * x566 + x565;
+  int x569 = x568 * x567 + x566;
+  int x570 = x569 * x568 + x567;
+  int x571 = x570 * x569 + x568;
+  int x572 = x571 * x570 + x569;
+  int x573 = x572 * x571 + x570;
+  int x574 = x573 * x572 + x571;
+  int x575 = x574 * x573 + x572;
+  int x576 = x575 * x574 + x573;
+  int x577 = x576 * x575 + x574;
+  int x578 = x577 * x576 + x575;
+  int x579 = x578 * x577 + x576;
+  int x580 = x579 * x578 + x577;
+  int x581 = x580 * x579 + x578;
+  int x582 = x581 * x580 + x579;
+  int x583 = x582 * x581 + x580;
+  int x584 = x583 * x582 + x581;
+  int x585 = x584 * x583 + x582;
+  int x586 = x585 * x584 + x583;
+  int x587 = x586 * x585 + x584;
+  int x588 = x587 * x586 + x585;
+  int x589 = x588 * x587 + x586;
+  int x590 = x589 * x588 + x587;
+  int x591 = x590 * x589 + x588;
+  int x592 = x591 * x590 + x589;
+  int x593 = x592 * x591 + x590;
+  int x594 = x593 * x592 + x591;
+  int x595 = x594 * x593 + x592;
+  int x596 = x595 * x594 + x593;
+  int x597 = x596 * x595 + x594;
+  int x598 = x597 * x596 + x595;
+  int x599 = x598 * x597 + x596;
+  int x600 = x599 * x598 + x597;
+
+  return x600;
+}