thodg/got

diff --git a/got/got.c b/got/got.c
index 9f023e7..33f2e98 100644
--- a/got/got.c
+++ b/got/got.c
@@ -270,62 +270,45 @@ check_cancelled(void *arg)
 }
 
 static const struct got_error *
-check_ancestry(struct got_worktree *worktree, struct got_object_id *commit_id,
-    struct got_repository *repo)
+check_linear_ancestry(struct got_worktree *worktree,
+    struct got_object_id *commit_id, struct got_repository *repo)
 {
-	const struct got_error *err;
-	struct got_reference *head_ref = NULL;
-	struct got_object_id *head_commit_id = NULL;
-	struct got_commit_graph *graph = NULL;
+	const struct got_error *err = NULL;
+	struct got_object_id *yca_id, *base_commit_id;
 
-	err = got_ref_open(&head_ref, repo,
-	    got_worktree_get_head_ref_name(worktree), 0);
+	base_commit_id = got_worktree_get_base_commit_id(worktree);
+	err = got_commit_graph_find_youngest_common_ancestor(&yca_id,
+	    commit_id, base_commit_id, repo);
 	if (err)
 		return err;
 
-	/* TODO: Check the reflog. The head ref may have been rebased. */
-	err = got_ref_resolve(&head_commit_id, repo, head_ref);
-	if (err)
-		goto done;
-
-	err = got_commit_graph_open(&graph, head_commit_id, "/", 1, repo);
-	if (err)
-		goto done;
-
-	err = got_commit_graph_iter_start(graph, head_commit_id, repo);
-	if (err)
-		goto done;
-	for (;;) {
-		struct got_object_id *id;
-
-		if (sigint_received || sigpipe_received)
-			break;
-
-		err = got_commit_graph_iter_next(&id, graph);
-		if (err) {
-			if (err->code == GOT_ERR_ITER_COMPLETED) {
-				err = got_error(GOT_ERR_ANCESTRY);
-				break;
-			}
-			if (err->code != GOT_ERR_ITER_NEED_MORE)
-				break;
-			err = got_commit_graph_fetch_commits(graph, 1, repo);
-			if (err)
-				break;
-			else
-				continue;
-		}
-		if (id == NULL)
-			break;
-		if (got_object_id_cmp(id, commit_id) == 0)
-			break;
-	}
-done:
-	if (head_ref)
-		got_ref_close(head_ref);
-	if (graph)
-		got_commit_graph_close(graph);
-	return err;
+	if (yca_id == NULL)
+		return got_error(GOT_ERR_ANCESTRY);
+
+	/*
+	 * Require a straight line of history between the target commit
+	 * and the work tree's base commit.
+	 *
+	 * Non-linear situation such as the this require a rebase:
+	 *
+	 * (commit) D       F (base_commit)
+	 *           \     /
+	 *            C   E
+	 *             \ /
+	 *              B (yca)
+	 *              |
+	 *              A
+	 *
+	 * 'got update' only handles linear cases:
+	 * Update forwards in time:  A (base/yca) - B - C - D (commit)
+	 * Update backwards in time: D (base) - C - D - A (commit/yca)
+	 */
+	if (got_object_id_cmp(commit_id, yca_id) != 0 &&
+	    got_object_id_cmp(base_commit_id, yca_id) != 0)
+		return got_error(GOT_ERR_ANCESTRY);
+
+	free(yca_id);
+	return NULL;
 }
 
 
@@ -452,7 +435,7 @@ cmd_checkout(int argc, char *argv[])
 		    commit_id_str);
 		if (error != NULL)
 			goto done;
-		error = check_ancestry(worktree, commit_id, repo);
+		error = check_linear_ancestry(worktree, commit_id, repo);
 		if (error != NULL) {
 			free(commit_id);
 			goto done;
@@ -581,7 +564,7 @@ cmd_update(int argc, char *argv[])
 			goto done;
 	}
 
-	error = check_ancestry(worktree, commit_id, repo);
+	error = check_linear_ancestry(worktree, commit_id, repo);
 	if (error != NULL)
 		goto done;
 
diff --git a/include/got_error.h b/include/got_error.h
index 2d5f5bd..8c60816 100644
--- a/include/got_error.h
+++ b/include/got_error.h
@@ -148,8 +148,7 @@ static const struct got_error {
 	{ GOT_ERR_FILEIDX_CSUM,	"bad file index checksum" },
 	{ GOT_ERR_PATH_PREFIX,	"worktree already contains items from a "
 				"different path prefix" },
-	{ GOT_ERR_ANCESTRY,	"specified commit does not share ancestry with "
-				"the current branch" },
+	{ GOT_ERR_ANCESTRY,	"new branch or rebase required" },
 	{ GOT_ERR_FILEIDX_BAD,	"file index is corrupt" },
 	{ GOT_ERR_BAD_REF_DATA,	"could not parse reference data" },
 	{ GOT_ERR_TREE_DUP_ENTRY,"duplicate entry in tree object" },
diff --git a/regress/cmdline/update.sh b/regress/cmdline/update.sh
index 5f2aab8..00c8418 100755
--- a/regress/cmdline/update.sh
+++ b/regress/cmdline/update.sh
@@ -1242,6 +1242,49 @@ function test_update_partial_dir {
 
 }
 
+function test_update_moved_branch_ref {
+	local testroot=`test_init update_moved_branch_ref`
+
+	git clone -q --mirror $testroot/repo $testroot/repo2
+
+	echo "modified alpha with git" > $testroot/repo/alpha
+	git_commit $testroot/repo -m "modified alpha with git"
+
+	got checkout $testroot/repo2 $testroot/wt > /dev/null
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	echo "modified alpha with got" > $testroot/wt/alpha
+	(cd $testroot/wt && got commit -m "modified alpha with got" > /dev/null)
+
+	# + xxxxxxx...yyyyyyy master     -> master  (forced update)
+	(cd $testroot/repo2 && git fetch -q --all)
+
+	echo -n > $testroot/stdout.expected
+	echo "got: new branch or rebase required" >> $testroot/stderr.expected
+
+	(cd $testroot/wt && got update > $testroot/stdout 2> $testroot/stderr)
+
+	cmp $testroot/stdout.expected $testroot/stdout
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		diff -u $testroot/stdout.expected $testroot/stdout
+		test_done "$testroot" "$ret"
+		return 1
+	fi
+
+	cmp $testroot/stderr.expected $testroot/stderr
+	ret="$?"
+	if [ "$ret" != "0" ]; then
+		diff -u $testroot/stderr.expected $testroot/stderr
+	fi
+	test_done "$testroot" "$ret"
+}
+
+
 run_test test_update_basic
 run_test test_update_adds_file
 run_test test_update_deletes_file
@@ -1267,3 +1310,4 @@ run_test test_update_partial
 run_test test_update_partial_add
 run_test test_update_partial_rm
 run_test test_update_partial_dir
+run_test test_update_moved_branch_ref