fix: pathological graph traversal in findMergeBase (#1057)

ef4 · billiegoose · commit 8e53088a69f4 · 2020-02-20T22:37:15.000-05:00
diff --git a/.all-contributorsrc b/.all-contributorsrc
@@ -378,6 +378,24 @@
         "doc",
         "test"
       ]
+    },
+    {
+      "login": "raon0211",
+      "name": "Sojin Park",
+      "avatar_url": "https://avatars1.githubusercontent.com/u/3102175?v=4",
+      "profile": "https://sojin.io",
+      "contributions": [
+        "code"
+      ]
+    },
+    {
+      "login": "ef4",
+      "name": "Edward Faulkner",
+      "avatar_url": "https://avatars0.githubusercontent.com/u/319282?v=4",
+      "profile": "https://eaf4.com",
+      "contributions": [
+        "code"
+      ]
     }
   ],
   "commitConvention": "angular"
diff --git a/README.md b/README.md
@@ -370,6 +370,8 @@ Thanks goes to these wonderful people ([emoji key](https://github.com/kentcdodds
   <tr>
     <td align="center"><a href="https://github.com/djencks"><img src="https://avatars2.githubusercontent.com/u/569822?v=4" width="60px;" alt="djencks"/><br /><sub><b>djencks</b></sub></a><br /><a href="https://github.com/isomorphic-git/isomorphic-git/issues?q=author%3Adjencks" title="Bug reports">🐛</a> <a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=djencks" title="Code">💻</a> <a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=djencks" title="Tests">⚠️</a></td>
     <td align="center"><a href="https://justamouse.com"><img src="https://avatars0.githubusercontent.com/u/1086421?v=4" width="60px;" alt="Clemens Wolff"/><br /><sub><b>Clemens Wolff</b></sub></a><br /><a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=c-w" title="Code">💻</a> <a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=c-w" title="Documentation">📖</a> <a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=c-w" title="Tests">⚠️</a></td>
+    <td align="center"><a href="https://sojin.io"><img src="https://avatars1.githubusercontent.com/u/3102175?v=4" width="60px;" alt="Sojin Park"/><br /><sub><b>Sojin Park</b></sub></a><br /><a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=raon0211" title="Code">💻</a></td>
+    <td align="center"><a href="https://eaf4.com"><img src="https://avatars0.githubusercontent.com/u/319282?v=4" width="60px;" alt="Edward Faulkner"/><br /><sub><b>Edward Faulkner</b></sub></a><br /><a href="https://github.com/isomorphic-git/isomorphic-git/commits?author=ef4" title="Code">💻</a></td>
   </tr>
 </table>
 
diff --git a/src/commands/findMergeBase.js b/src/commands/findMergeBase.js
@@ -43,7 +43,9 @@ export async function _findMergeBase({ fs, gitdir, oids }) {
         const commit = GitCommit.from(object)
         const { parent } = commit.parseHeaders()
         for (const oid of parent) {
-          newheads.push({ oid, index })
+          if (!visits[oid] || !visits[oid].has(index)) {
+            newheads.push({ oid, index })
+          }
         }
       } catch (err) {
         // do nothing
