Repository: iterative/dvc

Issue:
Use git/dvc APIs instead of actually checking out revisions
There are few DVC commands that accept `--all-branches` and `--all-tags` options. Namely,  [`dvc metrics show`](https://dvc.org/doc/commands-reference/metrics-show), [`dvc gc`](https://dvc.org/doc/commands-reference/gc), [`dvc fetch`](https://dvc.org/doc/commands-reference/fetch), etc. For all of them what we need is to being able to analyze content of DVC metafile across different Git revisions. Right now it's done by running `git checkout` (and then `dvc checkout` if we need to get content of the file from cache). This approach is fragile, depends on the current state of the working space (e.g there are uncommitted changes) and even [dangerous](https://github.com/iterative/dvc/issues/1552).

We should instead employ git API (like `ls-tree`, or `ls-files`?) and dvc API to get direct access to necessary files, directories, etc.

Current implementation is here: https://github.com/iterative/dvc/blob/master/dvc/scm/base.py#L79 and is used in two places: https://github.com/iterative/dvc/blob/master/dvc/repo/__init__.py#L239 and https://github.com/iterative/dvc/blob/master/dvc/repo/metrics/show.py#L144.

Directly related issue: https://github.com/iterative/dvc/issues/1009


Discussion:
ei-grad: @shcheklein 

> 1. Consistency in behavior for `dvc fetch -a` and `dvc fetch`. If there is only one branch? If there are multiple branches? Basically, do we (should we) check the working space files or only from Git when `-a` is specified.

Good point. I think the solution could be to add the `""` (empty branch) to the `brancher()` output in case if there are changes in the working tree, and it would be just like another one branch in the output. But it looks like a hack.

> Does is break the current behavior?

Just to clarify - the current behavior is to randomly fail with the error in case the working space has uncommitted changes. It could break down in the middle of the process on the checkout to the branch which have conflicting changes.

```
Error: unexpected error - Cmd('git') failed due to: exit code(1)
  cmdline: git checkout master
  stderr: 'error: Your local changes to the following files would be overwritten by checkout:
	metric
	metric_csv
	metric_hcsv
	metric_htsv
	metric_json
	metric_tsv
Please commit your changes or stash them before you switch branches.
```

> 2. The way we distinguish regular FS vs Git virtual. We pass `branch` and the logic to determine the exact function to call is spread across SCM, Stage, etc. (I mean code like `if branch ...`). It would be beneficial to pass around a class that implements fs operations (open, isdir, etc) instead. Something like OsFs, GitFs (it takes a revision name). `brancher` should return an iterator on these file system object. All these objects implement the same interface. All the high level code should not be even aware about all this revisions, branches, etc.

Sounds interesting, I like it. Do we mind to proceed with such refactoring in the scope of this PR?


ei-grad: > The way we distinguish regular FS vs Git virtual.
Also, there are related things about remote metrics etc. It should be thought carefully before implementing abstraction, imo.
shcheklein: 
> Just to clarify - the current behavior is to randomly fail with the error in case the working space has uncommitted changes. It could break down in the middle of the process on the checkout to the branch which have conflicting changes.

Just one of the examples from the top of my head. A repo with a single branch, run `dvc fetch -a` when there are uncommitted changes to the DVC files in the working space

Another example to try - we just ran `dvc run`  and there are DVC files that are not even tracked by Git yet (so, brancher won't be preventing checkouts). All commands that accept `-a` will be behave in a different way.

I'm not sure if there are other examples like this.

I'm not saying that we should keep the existing behavior - we just need to think a little bit what kind of behavior we actually need in case when we have something in the working space.

Passing empty branch sound like a hack indeed.

> Sounds interesting, I like it. Do we mind to proceed with such refactoring in the scope of this PR?

It does not sound like a big thing but can help encapsulate the logic related to choosing file system API in one place.

> 
> Btw, there are related things like remote metrics etc. It should be thought carefully before introducing this abstraction, imo.

This is true, but if feels a little bit orthogonal for now at least.



efiop: @ei-grad Great PR! Looking forward to the next iteration! :slightly_smiling_face: Thank you for your effort!
ei-grad: @shcheklein hm... if we took the both things together, I mean `-a` behaviour implementation and explicit file access abstraction, it looks for me like the right way to do.
ei-grad: Thank you all for the review and comments, I'll try to deal with this things until the weekend. Didn't have enough time to work last two days.
shcheklein: > @shcheklein hm... if we took the both things together, I mean `-a` behaviour implementation and explicit file access abstraction, it looks for me like the right way to go.

You mean that if we run something with `-a` it should include also the default access to the working space, right? It sounds good to me!

> Thank you all for the review and comments, I'll try to deal with this things until the weekend. Didn't have enough time to work last two days.

Sounds great! Thank you for the great PR.
ei-grad: oops, got some unrelated commits...

Patch:
diff --git a/dvc/__init__.py b/dvc/__init__.py
index 2293c96e6..1228f2df3 100644
--- a/dvc/__init__.py
+++ b/dvc/__init__.py
@@ -57,6 +57,7 @@ if os.path.exists(os.path.join(HOMEPATH, "setup.py")):
     if (
         os.getenv("APPVEYOR_REPO_TAG", "").lower() != "true"
         and os.getenv("TRAVIS_TAG", "") == ""
+        and os.getenv("DVC_TEST", "").lower() != "true"
     ):
         __version__ = _update_version_file()
     else:  # pragma: no cover
diff --git a/dvc/repo/__init__.py b/dvc/repo/__init__.py
index 2205eb234..ac55cb255 100644
--- a/dvc/repo/__init__.py
+++ b/dvc/repo/__init__.py
@@ -1,7 +1,5 @@
 from __future__ import unicode_literals
 
-from dvc.utils.compat import str
-
 import os
 import dvc.prompt as prompt
 import dvc.logger as logger
@@ -29,6 +27,7 @@ class Repo(object):
     from dvc.repo.gc import gc
     from dvc.repo.commit import commit
     from dvc.repo.pkg import install_pkg
+    from dvc.repo.brancher import brancher
 
     def __init__(self, root_dir=None):
         from dvc.config import Config
@@ -39,6 +38,7 @@ class Repo(object):
         from dvc.data_cloud import DataCloud
         from dvc.updater import Updater
         from dvc.repo.metrics import Metrics
+        from dvc.repo.tree import WorkingTree
 
         root_dir = self.find_root(root_dir)
 
@@ -47,6 +47,8 @@ class Repo(object):
 
         self.config = Config(self.dvc_dir)
 
+        self.tree = WorkingTree()
+
         self.scm = SCM(self.root_dir, repo=self)
         self.lock = Lock(self.dvc_dir)
         # NOTE: storing state and link_state in the repository itself to avoid
@@ -133,7 +135,7 @@ class Repo(object):
             raise CyclicGraphError(cycles[0])
 
     def _get_pipeline(self, node):
-        pipelines = list(filter(lambda g: node in g.nodes(), self.pipelines()))
+        pipelines = [i for i in self.pipelines() if i.has_node(node)]
         assert len(pipelines) == 1
         return pipelines[0]
 
@@ -147,11 +149,10 @@ class Repo(object):
 
         node = os.path.relpath(stage.path, self.root_dir)
         G = self._get_pipeline(node)
-        stages = nx.get_node_attributes(G, "stage")
 
-        ret = [stage]
+        ret = []
         for n in nx.dfs_postorder_nodes(G, node):
-            ret.append(stages[n])
+            ret.append(G.node[n]["stage"])
 
         return ret
 
@@ -244,7 +245,7 @@ class Repo(object):
         cache["ssh"] = []
         cache["azure"] = []
 
-        for branch in self.scm.brancher(
+        for branch in self.brancher(
             all_branches=all_branches, all_tags=all_tags
         ):
             if target:
@@ -361,10 +362,10 @@ class Repo(object):
 
         stages = []
         outs = []
-        for root, dirs, files in os.walk(str(from_directory)):
+        for root, dirs, files in self.tree.walk(from_directory):
             for fname in files:
                 path = os.path.join(root, fname)
-                if not Stage.is_stage_file(path):
+                if not Stage.is_valid_filename(path):
                     continue
                 stage = Stage.load(self, path)
                 for out in stage.outs:
@@ -397,10 +398,14 @@ class Repo(object):
 
     def find_outs_by_path(self, path, outs=None, recursive=False):
         if not outs:
-            outs = [out for stage in self.stages() for out in stage.outs]
+            # there is no `from_directory=path` argument because some data
+            # files might be generated to an upper level, and so it is
+            # needed to look at all the files (project root_dir)
+            stages = self.stages()
+            outs = [out for stage in stages for out in stage.outs]
 
         abs_path = os.path.abspath(path)
-        is_dir = os.path.isdir(abs_path)
+        is_dir = self.tree.isdir(abs_path)
 
         def func(out):
             if out.path == abs_path:
diff --git a/dvc/repo/brancher.py b/dvc/repo/brancher.py
new file mode 100644
index 000000000..6a4cfca13
--- /dev/null
+++ b/dvc/repo/brancher.py
@@ -0,0 +1,56 @@
+def brancher(  # noqa: E302
+    self, branches=None, all_branches=False, tags=None, all_tags=False
+):
+    """Generator that iterates over specified revisions.
+
+    Args:
+        branches (list): a list of branches to iterate over.
+        all_branches (bool): iterate over all available branches.
+        tags (list): a list of tags to iterate over.
+        all_tags (bool): iterate over all available tags.
+
+    Yields:
+        str: the display name for the currently selected tree, it could be:
+            - a git revision identifier
+            - empty string it there is no branches to iterate over
+            - "Working Tree" if there are uncommited changes in the SCM repo
+    """
+    if not any([branches, all_branches, tags, all_tags]):
+        yield ""
+        return
+
+    saved_tree = self.tree
+    revs = []
+
+    scm = self.scm
+
+    if self.scm.is_dirty():
+        from dvc.repo.tree import WorkingTree
+
+        self.tree = WorkingTree()
+        yield "Working Tree"
+
+    if all_branches:
+        branches = scm.list_branches()
+
+    if all_tags:
+        tags = scm.list_tags()
+
+    if branches is None:
+        revs.extend([scm.active_branch()])
+    else:
+        revs.extend(branches)
+
+    if tags is not None:
+        revs.extend(tags)
+
+    # NOTE: it might be a good idea to wrap this loop in try/finally block
+    # to don't leave the tree on some unexpected branch after the
+    # `brancher()`, but this could cause problems on exception handling
+    # code which might expect the tree on which exception was raised to
+    # stay in place. This behavior is a subject to change.
+    for rev in revs:
+        self.tree = scm.get_tree(rev)
+        yield rev
+
+    self.tree = saved_tree
diff --git a/dvc/repo/init.py b/dvc/repo/init.py
index 7311f20d3..dc23f223a 100644
--- a/dvc/repo/init.py
+++ b/dvc/repo/init.py
@@ -4,7 +4,7 @@ import colorama
 
 import dvc.logger as logger
 from dvc.repo import Repo
-from dvc.scm import SCM, Base
+from dvc.scm import SCM, NoSCM
 from dvc.config import Config
 from dvc.exceptions import InitError
 
@@ -56,7 +56,7 @@ def init(root_dir=os.curdir, no_scm=False, force=False):
     root_dir = os.path.abspath(root_dir)
     dvc_dir = os.path.join(root_dir, Repo.DVC_DIR)
     scm = SCM(root_dir)
-    if type(scm) == Base and not no_scm:
+    if isinstance(scm, NoSCM) and not no_scm:
         raise InitError(
             "{repo} is not tracked by any supported scm tool (e.g. git). "
             "Use '--no-scm' if you don't want to use any scm.".format(
diff --git a/dvc/repo/metrics/show.py b/dvc/repo/metrics/show.py
index f273d2c22..c4667bf5a 100644
--- a/dvc/repo/metrics/show.py
+++ b/dvc/repo/metrics/show.py
@@ -66,30 +66,23 @@ def _read_typed_metric(typ, xpath, fd):
     return ret
 
 
-def _read_metric(path, typ=None, xpath=None, branch=None):
-    ret = None
-    if not os.path.exists(path):
-        return ret
-
+def _read_metric(fd, typ=None, xpath=None, rel_path=None, branch=None):
     typ = typ.lower().strip() if typ else typ
-    xpath = xpath.strip() if xpath else xpath
     try:
-        with open(path, "r") as fd:
-            if not xpath:
-                ret = fd.read().strip()
-            else:
-                ret = _read_typed_metric(typ, xpath, fd)
+        if xpath:
+            return _read_typed_metric(typ, xpath.strip(), fd)
+        else:
+            return fd.read().strip()
     # Json path library has to be replaced or wrapped in
     # order to fix this too broad except clause.
     except Exception:
         logger.warning(
             "unable to read metric in '{}' in branch '{}'".format(
-                path, branch
+                rel_path, branch
             ),
             parse_exception=True,
         )
-
-    return ret
+        return None
 
 
 def _collect_metrics(self, path, recursive, typ, xpath, branch):
@@ -123,16 +116,33 @@ def _collect_metrics(self, path, recursive, typ, xpath, branch):
     return res
 
 
+def _read_metrics_filesystem(path, typ, xpath, rel_path, branch):
+    if not os.path.exists(path):
+        return None
+    with open(path, "r") as fd:
+        return _read_metric(
+            fd, typ=typ, xpath=xpath, rel_path=rel_path, branch=branch
+        )
+
+
 def _read_metrics(self, metrics, branch):
     res = {}
     for out, typ, xpath in metrics:
         assert out.scheme == "local"
         if out.use_cache:
-            path = self.cache.local.get(out.checksum)
+            metric = _read_metrics_filesystem(
+                self.cache.local.get(out.checksum),
+                typ=typ,
+                xpath=xpath,
+                rel_path=out.rel_path,
+                branch=branch,
+            )
         else:
-            path = out.path
+            fd = self.tree.open(out.path)
+            metric = _read_metric(
+                fd, typ=typ, xpath=xpath, rel_path=out.rel_path, branch=branch
+            )
 
-        metric = _read_metric(path, typ=typ, xpath=xpath, branch=branch)
         if not metric:
             continue
 
@@ -151,9 +161,8 @@ def show(
     recursive=False,
 ):
     res = {}
-    for branch in self.scm.brancher(
-        all_branches=all_branches, all_tags=all_tags
-    ):
+
+    for branch in self.brancher(all_branches=all_branches, all_tags=all_tags):
         entries = _collect_metrics(self, path, recursive, typ, xpath, branch)
         metrics = _read_metrics(self, entries, branch)
         if metrics:
diff --git a/dvc/repo/tree.py b/dvc/repo/tree.py
new file mode 100644
index 000000000..3e215ff09
--- /dev/null
+++ b/dvc/repo/tree.py
@@ -0,0 +1,65 @@
+import os
+
+from dvc.utils.compat import open
+
+
+class BaseTree(object):
+    """Abstract class to represent access to files"""
+
+    def open(self, path):
+        """Open file and return a stream."""
+
+    def exists(self, path):
+        """Test whether a path exists."""
+
+    def isdir(self, path):
+        """Return true if the pathname refers to an existing directory."""
+
+    def isfile(self, path):
+        """Test whether a path is a regular file"""
+
+    def walk(self, top, topdown=True):
+        """Directory tree generator.
+
+        See `os.walk` for the docs. Differences:
+        - no support for symlinks
+        - it could raise exceptions, there is no onerror argument
+        """
+
+
+class WorkingTree(BaseTree):
+    """Proxies the repo file access methods to working tree files"""
+
+    def open(self, path):
+        """Open file and return a stream."""
+        return open(path, encoding="utf-8")
+
+    def exists(self, path):
+        """Test whether a path exists."""
+        return os.path.exists(path)
+
+    def isdir(self, path):
+        """Return true if the pathname refers to an existing directory."""
+        return os.path.isdir(path)
+
+    def isfile(self, path):
+        """Test whether a path is a regular file"""
+        return os.path.isfile(path)
+
+    def walk(self, top, topdown=True):
+        """Directory tree generator.
+
+        See `os.walk` for the docs. Differences:
+        - no support for symlinks
+        - it could raise exceptions, there is no onerror argument
+        """
+
+        def onerror(e):
+            raise e
+
+        for root, dirs, files in os.walk(
+            top, topdown=topdown, onerror=onerror
+        ):
+            if topdown:
+                dirs[:] = [i for i in dirs if i not in (".git", ".hg", ".dvc")]
+            yield os.path.normpath(root), dirs, files
diff --git a/dvc/scm/__init__.py b/dvc/scm/__init__.py
index e3f2f4b63..c5f8d20d7 100644
--- a/dvc/scm/__init__.py
+++ b/dvc/scm/__init__.py
@@ -8,6 +8,12 @@ from dvc.scm.git import Git
 import dvc
 
 
+# just a sugar to point that this is an actual implementation for a dvc
+# project under no SCM control
+class NoSCM(Base):
+    pass
+
+
 def SCM(root_dir, repo=None):  # pylint: disable=invalid-name
     """Returns SCM instance that corresponds to a repo at the specified
     path.
@@ -22,7 +28,7 @@ def SCM(root_dir, repo=None):  # pylint: disable=invalid-name
     if Git.is_repo(root_dir) or Git.is_submodule(root_dir):
         return Git(root_dir, repo=repo)
 
-    return Base(root_dir, repo=repo)
+    return NoSCM(root_dir, repo=repo)
 
 
 def scm_context(method):
diff --git a/dvc/scm/base.py b/dvc/scm/base.py
index eb957f030..dc2dde69e 100644
--- a/dvc/scm/base.py
+++ b/dvc/scm/base.py
@@ -81,47 +81,6 @@ class Base(object):
     def tag(self, tag):
         """Makes SCM create a tag with a specified name."""
 
-    def brancher(
-        self, branches=None, all_branches=False, tags=None, all_tags=False
-    ):
-        """Generator that iterates over specified revisions.
-
-        Args:
-            branches (list): a list of branches to iterate over.
-            all_branches (bool): iterate over all available branches.
-            tags (list): a list of tags to iterate over.
-            all_tags (bool): iterate over all available tags.
-
-        Yields:
-            str: the current revision.
-        """
-        if not branches and not all_branches and not tags and not all_tags:
-            yield ""
-            return
-
-        saved = self.active_branch()
-        revs = []
-
-        if all_branches:
-            branches = self.list_branches()
-
-        if all_tags:
-            tags = self.list_tags()
-
-        if branches is None:
-            revs.extend([saved])
-        else:
-            revs.extend(branches)
-
-        if tags is not None:
-            revs.extend(tags)
-
-        for rev in revs:
-            self.checkout(rev)
-            yield rev
-
-        self.checkout(saved)
-
     def untracked_files(self):  # pylint: disable=no-self-use
         """Returns a list of untracked files."""
         return []
@@ -130,6 +89,10 @@ class Base(object):
         """Returns whether or not a specified path is tracked."""
         return False
 
+    def is_dirty(self):
+        """Return whether the SCM contains uncommited changes."""
+        return False
+
     def active_branch(self):  # pylint: disable=no-self-use
         """Returns current branch in the repo."""
         return ""
diff --git a/dvc/scm/git.py b/dvc/scm/git/__init__.py
similarity index 93%
rename from dvc/scm/git.py
rename to dvc/scm/git/__init__.py
index 4000f92bd..cd585f841 100644
--- a/dvc/scm/git.py
+++ b/dvc/scm/git/__init__.py
@@ -2,15 +2,9 @@
 
 from __future__ import unicode_literals
 
-# NOTE: need this one because python 2 would re-import this module
-# (called git.py) instead of importing gitpython's git module.
-from __future__ import absolute_import
-
-from dvc.utils.compat import str, open
-
 import os
 
-import dvc.logger as logger
+from dvc.utils.compat import str, open
 from dvc.utils import fix_env
 from dvc.scm.base import (
     Base,
@@ -18,6 +12,8 @@ from dvc.scm.base import (
     FileNotInRepoError,
     FileNotInTargetSubdirError,
 )
+from dvc.scm.git.tree import GitTree
+import dvc.logger as logger
 
 
 class Git(Base):
@@ -126,7 +122,7 @@ class Git(Base):
         content = entry
         if ignore_list:
             content = "\n" + content
-        with open(gitignore, "a") as fobj:
+        with open(gitignore, "a", encoding="utf-8") as fobj:
             fobj.write(content)
 
     def ignore_remove(self, path):
@@ -180,7 +176,13 @@ class Git(Base):
         return [os.path.join(self.git.working_dir, fname) for fname in files]
 
     def is_tracked(self, path):
-        return len(self.git.git.ls_files(path)) != 0
+        # it is equivalent to `bool(self.git.git.ls_files(path))` by
+        # functionality, but ls_files fails on unicode filenames
+        path = os.path.relpath(path, self.root_dir)
+        return path in [i[0] for i in self.git.index.entries]
+
+    def is_dirty(self):
+        return self.git.is_dirty()
 
     def active_branch(self):
         return self.git.active_branch.name
@@ -230,3 +232,6 @@ class Git(Base):
         basename = os.path.basename(path)
         path_parts = os.path.normpath(path).split(os.path.sep)
         return basename == self.ignore_file or Git.GIT_DIR in path_parts
+
+    def get_tree(self, rev):
+        return GitTree(self.git, rev)
diff --git a/dvc/scm/git/tree.py b/dvc/scm/git/tree.py
new file mode 100644
index 000000000..d9c56293e
--- /dev/null
+++ b/dvc/scm/git/tree.py
@@ -0,0 +1,114 @@
+import errno
+import os
+
+from dvc.utils.compat import StringIO
+
+from dvc.repo.tree import BaseTree
+
+
+# see git-fast-import(1)
+GIT_MODE_DIR = 0o40000
+GIT_MODE_FILE = 0o644
+
+
+class GitTree(BaseTree):
+    """Proxies the repo file access methods to Git objects"""
+
+    def __init__(self, git, rev):
+        """Create GitTree instance
+
+        Args:
+            git (dvc.scm.Git):
+            branch:
+        """
+        self.git = git
+        self.rev = rev
+
+    def open(self, path):
+
+        relpath = os.path.relpath(path, self.git.working_dir)
+
+        obj = self.git_object_by_path(path)
+        if obj is None:
+            msg = "No such file in branch '{}'".format(self.rev)
+            raise IOError(errno.ENOENT, msg, relpath)
+        if obj.mode == GIT_MODE_DIR:
+            raise IOError(errno.EISDIR, "Is a directory", relpath)
+
+        # GitPython's obj.data_stream is a fragile thing, it is better to
+        # read it immediately, also it needs to be to decoded if we follow
+        # the `open()` behavior (since data_stream.read() returns bytes,
+        # and `open` with default "r" mode returns str)
+        return StringIO(obj.data_stream.read().decode("utf-8"))
+
+    def exists(self, path):
+        return self.git_object_by_path(path) is not None
+
+    def isdir(self, path):
+        obj = self.git_object_by_path(path)
+        if obj is None:
+            return False
+        return obj.mode == GIT_MODE_DIR
+
+    def isfile(self, path):
+        obj = self.git_object_by_path(path)
+        if obj is None:
+            return False
+        # according to git-fast-import(1) file mode could be 644 or 755
+        return obj.mode & GIT_MODE_FILE == GIT_MODE_FILE
+
+    @staticmethod
+    def _is_tree_and_contains(obj, path):
+        if obj.mode != GIT_MODE_DIR:
+            return False
+        # see https://github.com/gitpython-developers/GitPython/issues/851
+        # `return (i in tree)` doesn't work so here is a workaround:
+        for i in obj:
+            if i.name == path:
+                return True
+        return False
+
+    def git_object_by_path(self, path):
+        path = os.path.relpath(os.path.realpath(path), self.git.working_dir)
+        assert path.split(os.sep, 1)[0] != ".."
+        tree = self.git.tree(self.rev)
+        if not path or path == ".":
+            return tree
+        for i in path.split(os.sep):
+            if not self._is_tree_and_contains(tree, i):
+                # there is no tree for specified path
+                return None
+            tree = tree[i]
+        return tree
+
+    def _walk(self, tree, topdown=True):
+
+        dirs, nondirs = [], []
+        for i in tree:
+            if i.mode == GIT_MODE_DIR:
+                dirs.append(i.name)
+            else:
+                nondirs.append(i.name)
+
+        if topdown:
+            yield os.path.normpath(tree.path), dirs, nondirs
+        for i in dirs:
+            for x in self._walk(tree[i], topdown=True):
+                yield x
+        if not topdown:
+            yield os.path.normpath(tree.path), dirs, nondirs
+
+    def walk(self, top, topdown=True):
+        """Directory tree generator.
+
+        See `os.walk` for the docs. Differences:
+        - no support for symlinks
+        - it could raise exceptions, there is no onerror argument
+        """
+
+        tree = self.git_object_by_path(top)
+        if tree is None:
+            raise IOError(errno.ENOENT, "No such file")
+
+        for x in self._walk(tree, topdown):
+            yield x
diff --git a/dvc/stage.py b/dvc/stage.py
index c8b7bc491..89eaf26f4 100644
--- a/dvc/stage.py
+++ b/dvc/stage.py
@@ -14,7 +14,7 @@ import dvc.logger as logger
 import dvc.dependency as dependency
 import dvc.output as output
 from dvc.exceptions import DvcException
-from dvc.utils import dict_md5, fix_env, load_stage_file
+from dvc.utils import dict_md5, fix_env, load_stage_file_fobj
 
 
 class StageCmdFailedError(DvcException):
@@ -171,7 +171,10 @@ class Stage(object):
     @staticmethod
     def is_valid_filename(path):
         return (
-            path.endswith(Stage.STAGE_FILE_SUFFIX)
+            # path.endswith doesn't work for encoded unicode filenames on
+            # Python 2 and since Stage.STAGE_FILE_SUFFIX is ascii then it is
+            # not needed to decode the path from py2's str
+            path[-len(Stage.STAGE_FILE_SUFFIX) :] == Stage.STAGE_FILE_SUFFIX
             or os.path.basename(path) == Stage.STAGE_FILE
         )
 
@@ -488,19 +491,27 @@ class Stage(object):
             )
 
     @staticmethod
-    def _check_file_exists(fname):
-        if not os.path.exists(fname):
+    def _check_file_exists(repo, fname):
+        if not repo.tree.exists(fname):
             raise StageFileDoesNotExistError(fname)
 
+    @staticmethod
+    def _check_isfile(repo, fname):
+        if not repo.tree.isfile(fname):
+            raise StageFileIsNotDvcFileError(fname)
+
     @staticmethod
     def load(repo, fname):
-        Stage._check_file_exists(fname)
-        Stage._check_dvc_filename(fname)
 
-        if not Stage.is_stage_file(fname):
-            raise StageFileIsNotDvcFileError(fname)
+        # it raises the proper exceptions by priority:
+        # 1. when the file doesn't exists
+        # 2. filename is not a dvc filename
+        # 3. path doesn't represent a regular file
+        Stage._check_file_exists(repo, fname)
+        Stage._check_dvc_filename(fname)
+        Stage._check_isfile(repo, fname)
 
-        d = load_stage_file(fname)
+        d = load_stage_file_fobj(repo.tree.open(fname), fname)
 
         Stage.validate(d, fname=os.path.relpath(fname))
         path = os.path.abspath(fname)
diff --git a/dvc/utils/__init__.py b/dvc/utils/__init__.py
index 58ae4cd5b..624edc7ab 100644
--- a/dvc/utils/__init__.py
+++ b/dvc/utils/__init__.py
@@ -232,13 +232,17 @@ def current_timestamp():
 
 
 def load_stage_file(path):
+    with open(path, "r") as fobj:
+        return load_stage_file_fobj(fobj, path)
+
+
+def load_stage_file_fobj(fobj, path):
     from dvc.exceptions import StageFileCorruptedError
 
-    with open(path, "r") as fobj:
-        try:
-            return yaml.safe_load(fobj) or {}
-        except ScannerError:
-            raise StageFileCorruptedError(path)
+    try:
+        return yaml.safe_load(fobj) or {}
+    except ScannerError:
+        raise StageFileCorruptedError(path)
 
 
 def walk_files(directory):


Test patch:
diff --git a/tests/basic_env.py b/tests/basic_env.py
index 05416178d..340c8fb6a 100644
--- a/tests/basic_env.py
+++ b/tests/basic_env.py
@@ -1,3 +1,7 @@
+# encoding: utf-8
+
+from __future__ import unicode_literals
+
 import os
 import shutil
 import uuid
@@ -10,6 +14,7 @@ from unittest import TestCase
 import dvc.logger as logger
 from dvc.command.remote import CmdRemoteAdd
 from dvc.repo import Repo as DvcRepo
+from dvc.utils.compat import open, str
 
 
 class TestDirFixture(object):
@@ -40,6 +45,8 @@ class TestDirFixture(object):
         "import sys\nimport shutil\n"
         "shutil.copyfile(sys.argv[1], sys.argv[2])"
     )
+    UNICODE = "тест"
+    UNICODE_CONTENTS = "проверка"
 
     def __init__(self, root_dir=None):
         if root_dir:
@@ -61,8 +68,12 @@ class TestDirFixture(object):
         if len(dname) > 0 and not os.path.isdir(dname):
             os.makedirs(dname)
 
-        with open(name, "a") as f:
-            f.write(contents)
+        with open(name, "a", encoding="utf-8") as f:
+            f.write(
+                contents
+                if isinstance(contents, str)
+                else contents.decode("utf-8")
+            )
 
     @staticmethod
     def mkdtemp():
@@ -79,6 +90,7 @@ class TestDirFixture(object):
         os.mkdir(self.DATA_SUB_DIR)
         self.create(self.DATA, self.DATA_CONTENTS)
         self.create(self.DATA_SUB, self.DATA_SUB_CONTENTS)
+        self.create(self.UNICODE, self.UNICODE_CONTENTS)
 
     def tearDown(self):
         self._popd()
@@ -126,6 +138,7 @@ class TestDvcFixture(TestGitFixture):
     def setUp(self):
         super(TestDvcFixture, self).setUp()
         self.dvc = DvcRepo.init(self._root_dir)
+        self.dvc.scm.commit("init dvc")
         logger.be_verbose()
 
 
diff --git a/tests/test_add.py b/tests/test_add.py
index e0618424c..995846d4a 100644
--- a/tests/test_add.py
+++ b/tests/test_add.py
@@ -475,7 +475,7 @@ class TestShouldCleanUpAfterFailedAdd(TestDvc):
         self.assertFalse(os.path.exists(bar_stage_file))
 
         gitignore_content = get_gitignore_content()
-        self.assertFalse(any(self.BAR in line for line in gitignore_content))
+        self.assertNotIn("/" + self.BAR, gitignore_content)
 
 
 class TestShouldNotTrackGitInternalFiles(TestDvc):
diff --git a/tests/test_install.py b/tests/test_install.py
index ec865b72e..df0c45403 100644
--- a/tests/test_install.py
+++ b/tests/test_install.py
@@ -1,10 +1,15 @@
 import os
+import sys
+import unittest
 
 from dvc.main import main
 
 from tests.basic_env import TestDvc
 
 
+@unittest.skipIf(
+    sys.platform == "win32", "Git hooks aren't supported on Windows"
+)
 class TestInstall(TestDvc):
     def test(self):
         ret = main(["install"])
@@ -20,6 +25,8 @@ class TestInstall(TestDvc):
         self.assertTrue(os.path.isfile(hook("pre-commit")))
 
         self.dvc.add(self.FOO)
+        self.dvc.scm.add([".gitignore", self.FOO + ".dvc"])
+        self.dvc.scm.commit("add")
         os.unlink(self.FOO)
 
         self.dvc.scm.checkout("branch", create_new=True)
diff --git a/tests/test_metrics.py b/tests/test_metrics.py
index 78456381b..523a72342 100644
--- a/tests/test_metrics.py
+++ b/tests/test_metrics.py
@@ -109,7 +109,7 @@ class TestMetrics(TestDvc):
         )
         self.assertEqual(len(ret), 3)
         for b in ["foo", "bar", "baz"]:
-            self.assertSequenceEqual(ret[b]["metric_hcsv"], "branch\n" + b)
+            self.assertEqual(ret[b]["metric_hcsv"].split(), ["branch", b])
 
     def test_type_case_normalized(self):
         ret = self.dvc.metrics.show(
@@ -206,7 +206,9 @@ class TestMetricsRecursive(TestDvc):
 
         self.assertEqual(ret, 0)
 
-        self.dvc.scm.add(["nested"])
+        self.dvc.scm.add(
+            ["nested", "metric_nested.dvc", "metric_subnested.dvc"]
+        )
         self.dvc.scm.commit("nested metrics")
 
         self.dvc.scm.checkout("master")
@@ -489,7 +491,7 @@ class TestCachedMetrics(TestDvc):
         self.assertIsNotNone(stage)
         self.assertEqual(stage.relpath, "metrics.json.dvc")
 
-        self.dvc.scm.add([".gitignore", "metrics.json.dvc"])
+        self.dvc.scm.add(["code.py", ".gitignore", "metrics.json.dvc"])
         self.dvc.scm.commit(branch)
 
     def _test_metrics(self, func):
@@ -502,6 +504,10 @@ class TestCachedMetrics(TestDvc):
         func("one")
         func("two")
 
+        # TestDvc currently is based on TestGit, so it is safe to use
+        # scm.git for now
+        self.dvc.scm.git.git.clean("-fd")
+
         self.dvc = DvcRepo(".")
 
         res = self.dvc.metrics.show(
diff --git a/tests/test_repo.py b/tests/test_repo.py
new file mode 100644
index 000000000..0a99533af
--- /dev/null
+++ b/tests/test_repo.py
@@ -0,0 +1,46 @@
+from tests.basic_env import TestDvc
+
+from dvc.scm.git import GitTree
+from dvc.repo.tree import WorkingTree
+
+
+class TestCollect(TestDvc):
+    def setUp(self):
+        super(TestCollect, self).setUp()
+        self.dvc.add(self.FOO)
+        self.dvc.run(
+            deps=[self.FOO],
+            outs=[self.BAR],
+            cmd="python code.py {} {}".format(self.FOO, self.BAR),
+        )
+        self.dvc.scm.add([".gitignore", self.FOO + ".dvc", self.BAR + ".dvc"])
+        self.dvc.scm.commit("foo.dvc and bar.dvc")
+        self.dvc.scm.checkout("new_branch", True)
+        self.dvc.run(
+            deps=[self.BAR],
+            outs=["buzz"],
+            cmd="python code.py {} {}".format(self.BAR, "buzz"),
+        )
+        self.dvc.scm.add([".gitignore", "buzz.dvc"])
+        self.dvc.scm.commit("add buzz")
+        self.dvc.scm.checkout("master")
+
+    def _check(self, branch, target, with_deps, expected):
+        if branch:
+            self.dvc.tree = GitTree(self.dvc.scm.git, branch)
+        else:
+            self.dvc.tree = WorkingTree()
+        result = self.dvc.collect(target + ".dvc", with_deps=with_deps)
+        self.assertEqual(
+            [[j.rel_path for j in i.outs] for i in result], expected
+        )
+        return result
+
+    def test(self):
+        self._check("", self.BAR, True, [[self.FOO], [self.BAR]])
+        self._check("master", self.BAR, True, [[self.FOO], [self.BAR]])
+        self._check(
+            "new_branch", "buzz", True, [[self.FOO], [self.BAR], ["buzz"]]
+        )
+        result = self._check("new_branch", "buzz", False, [["buzz"]])
+        self.assertEqual([i.rel_path for i in result[0].deps], ["bar"])
diff --git a/tests/test_scm.py b/tests/test_scm.py
index 7bf7e3726..885b9c613 100644
--- a/tests/test_scm.py
+++ b/tests/test_scm.py
@@ -1,10 +1,11 @@
 from __future__ import unicode_literals
 
 import os
+
 from git import Repo
 
 from dvc.utils.compat import str  # noqa: F401
-from dvc.scm import SCM, Base, Git
+from dvc.scm import SCM, NoSCM, Git
 from dvc.scm.base import FileNotInTargetSubdirError
 
 from tests.basic_env import TestDir, TestGit, TestGitSubmodule
@@ -13,7 +14,7 @@ from tests.utils import get_gitignore_content
 
 class TestSCM(TestDir):
     def test_none(self):
-        self.assertIsInstance(SCM(self._root_dir), Base)
+        self.assertIsInstance(SCM(self._root_dir), NoSCM)
 
     def test_git(self):
         Repo.init(os.curdir)
@@ -28,7 +29,22 @@ class TestSCMGit(TestGit):
         G = Git(self._root_dir)
         G.add(["foo"])
         G.commit("add")
-        self.assertTrue("foo" in self.git.git.ls_files())
+        self.assertIn("foo", self.git.git.ls_files())
+
+    def test_is_tracked(self):
+        foo = os.path.abspath(self.FOO)
+        G = Git(self._root_dir)
+        G.add([self.FOO, self.UNICODE])
+        self.assertTrue(G.is_tracked(foo))
+        self.assertTrue(G.is_tracked(self.FOO))
+        self.assertTrue(G.is_tracked(self.UNICODE))
+        G.commit("add")
+        self.assertTrue(G.is_tracked(foo))
+        self.assertTrue(G.is_tracked(self.FOO))
+        G.git.index.remove([self.FOO], working_tree=True)
+        self.assertFalse(G.is_tracked(foo))
+        self.assertFalse(G.is_tracked(self.FOO))
+        self.assertFalse(G.is_tracked("not-existing-file"))
 
 
 class TestSCMGitSubmodule(TestGitSubmodule):
@@ -48,8 +64,7 @@ class TestSCMGitSubmodule(TestGitSubmodule):
 class TestIgnore(TestGit):
     def _count_gitignore(self):
         lines = get_gitignore_content()
-
-        return len(list(filter(lambda x: x.strip() == "/" + self.FOO, lines)))
+        return len([i for i in lines if i == "/" + self.FOO])
 
     def test_ignore(self):
         git = Git(self._root_dir)
diff --git a/tests/test_tree.py b/tests/test_tree.py
new file mode 100644
index 000000000..de81f8093
--- /dev/null
+++ b/tests/test_tree.py
@@ -0,0 +1,150 @@
+# encoding: utf-8
+
+from __future__ import unicode_literals
+
+from os.path import join
+
+from dvc.scm import SCM
+from dvc.scm.git import GitTree
+from dvc.repo.tree import WorkingTree
+
+from tests.basic_env import TestDir, TestGit
+
+
+class TestWorkingTree(TestDir):
+    def setUp(self):
+        super(TestWorkingTree, self).setUp()
+        self.tree = WorkingTree()
+
+    def test_open(self):
+        self.assertEqual(self.tree.open(self.FOO).read(), self.FOO_CONTENTS)
+        self.assertEqual(
+            self.tree.open(self.UNICODE).read(), self.UNICODE_CONTENTS
+        )
+
+    def test_exists(self):
+        self.assertTrue(self.tree.exists(self.FOO))
+        self.assertTrue(self.tree.exists(self.UNICODE))
+        self.assertFalse(self.tree.exists("not-existing-file"))
+
+    def test_isdir(self):
+        self.assertTrue(self.tree.isdir(self.DATA_DIR))
+        self.assertFalse(self.tree.isdir(self.FOO))
+        self.assertFalse(self.tree.isdir("not-existing-file"))
+
+    def test_isfile(self):
+        self.assertTrue(self.tree.isfile(self.FOO))
+        self.assertFalse(self.tree.isfile(self.DATA_DIR))
+        self.assertFalse(self.tree.isfile("not-existing-file"))
+
+
+class TestGitTree(TestGit):
+    def setUp(self):
+        super(TestGitTree, self).setUp()
+        self.scm = SCM(self._root_dir)
+        self.tree = GitTree(self.git, "master")
+
+    def test_open(self):
+        self.scm.add([self.FOO, self.UNICODE, self.DATA_DIR])
+        self.scm.commit("add")
+        self.assertEqual(self.tree.open(self.FOO).read(), self.FOO_CONTENTS)
+        self.assertEqual(
+            self.tree.open(self.UNICODE).read(), self.UNICODE_CONTENTS
+        )
+        with self.assertRaises(IOError):
+            self.tree.open("not-existing-file")
+        with self.assertRaises(IOError):
+            self.tree.open(self.DATA_DIR)
+
+    def test_exists(self):
+        self.assertFalse(self.tree.exists(self.FOO))
+        self.assertFalse(self.tree.exists(self.UNICODE))
+        self.assertFalse(self.tree.exists(self.DATA_DIR))
+        self.scm.add([self.FOO, self.UNICODE, self.DATA])
+        self.scm.commit("add")
+        self.assertTrue(self.tree.exists(self.FOO))
+        self.assertTrue(self.tree.exists(self.UNICODE))
+        self.assertTrue(self.tree.exists(self.DATA_DIR))
+        self.assertFalse(self.tree.exists("non-existing-file"))
+
+    def test_isdir(self):
+        self.scm.add([self.FOO, self.DATA_DIR])
+        self.scm.commit("add")
+        self.assertTrue(self.tree.isdir(self.DATA_DIR))
+        self.assertFalse(self.tree.isdir(self.FOO))
+        self.assertFalse(self.tree.isdir("non-existing-file"))
+
+    def test_isfile(self):
+        self.scm.add([self.FOO, self.DATA_DIR])
+        self.scm.commit("add")
+        self.assertTrue(self.tree.isfile(self.FOO))
+        self.assertFalse(self.tree.isfile(self.DATA_DIR))
+        self.assertFalse(self.tree.isfile("not-existing-file"))
+
+
+class AssertWalkEqualMixin(object):
+    def assertWalkEqual(self, actual, expected, msg=None):
+        def convert_to_sets(walk_results):
+            return [
+                (root, set(dirs), set(nondirs))
+                for root, dirs, nondirs in walk_results
+            ]
+
+        self.assertEqual(
+            convert_to_sets(actual), convert_to_sets(expected), msg=msg
+        )
+
+
+class TestWalkInNoSCM(AssertWalkEqualMixin, TestDir):
+    def test(self):
+        tree = WorkingTree()
+        self.assertWalkEqual(
+            tree.walk("."),
+            [
+                (".", ["data_dir"], ["code.py", "bar", "тест", "foo"]),
+                (join("data_dir"), ["data_sub_dir"], ["data"]),
+                (join("data_dir", "data_sub_dir"), [], ["data_sub"]),
+            ],
+        )
+
+    def test_subdir(self):
+        tree = WorkingTree()
+        self.assertWalkEqual(
+            tree.walk(join("data_dir", "data_sub_dir")),
+            [(join("data_dir", "data_sub_dir"), [], ["data_sub"])],
+        )
+
+
+class TestWalkInGit(AssertWalkEqualMixin, TestGit):
+    def test_nobranch(self):
+        tree = WorkingTree()
+        self.assertWalkEqual(
+            tree.walk("."),
+            [
+                (".", ["data_dir"], ["bar", "тест", "code.py", "foo"]),
+                ("data_dir", ["data_sub_dir"], ["data"]),
+                (join("data_dir", "data_sub_dir"), [], ["data_sub"]),
+            ],
+        )
+        self.assertWalkEqual(
+            tree.walk(join("data_dir", "data_sub_dir")),
+            [(join("data_dir", "data_sub_dir"), [], ["data_sub"])],
+        )
+
+    def test_branch(self):
+        scm = SCM(self._root_dir)
+        scm.add([self.DATA_SUB_DIR])
+        scm.commit("add data_dir/data_sub_dir/data_sub")
+        tree = GitTree(self.git, "master")
+        self.assertWalkEqual(
+            tree.walk("."),
+            [
+                (".", ["data_dir"], ["code.py"]),
+                ("data_dir", ["data_sub_dir"], []),
+                (join("data_dir", "data_sub_dir"), [], ["data_sub"]),
+            ],
+        )
+        self.assertWalkEqual(
+            tree.walk(join("data_dir", "data_sub_dir")),
+            [(join("data_dir", "data_sub_dir"), [], ["data_sub"])],
+        )
diff --git a/tests/unit/scm/test_scm.py b/tests/unit/scm/test_scm.py
index 40061bd3a..4a7ede011 100644
--- a/tests/unit/scm/test_scm.py
+++ b/tests/unit/scm/test_scm.py
@@ -1,5 +1,5 @@
 from dvc.repo import Repo
-from dvc.scm import scm_context, Base
+from dvc.scm import scm_context, NoSCM
 from unittest import TestCase
 import mock
 
@@ -7,7 +7,7 @@ import mock
 class TestScmContext(TestCase):
     def setUp(self):
         self.repo_mock = mock.Mock(spec=Repo)
-        self.scm_mock = mock.Mock(spec=Base)
+        self.scm_mock = mock.Mock(spec=NoSCM)
         self.repo_mock.scm = self.scm_mock
 
     def test_should_successfully_perform_method(self):
diff --git a/tests/utils/__init__.py b/tests/utils/__init__.py
index 39bb8be57..7f3d5e282 100644
--- a/tests/utils/__init__.py
+++ b/tests/utils/__init__.py
@@ -20,7 +20,7 @@ def spy(method_to_decorate):
 
 def get_gitignore_content():
     with open(Git.GITIGNORE, "r") as gitignore:
-        return gitignore.readlines()
+        return gitignore.read().splitlines()
 
 
 def load_stage_file(path):