Repository: microsoft/pybryt

Issue:
Caching mechanism for checks
Implement a mechanism for caching the memory footprints (and results?) generated from checks.

Thinking of pickling the footprints/results and storing the files in a hidden `.pybryt_cache` directory within the working directory. Use a filename structure like `{ref.name}_footprint.pkl` and `{ref.name}_results.pkl`.

Discussion:

Patch:
diff --git a/.gitignore b/.gitignore
index ab96fc4..eb9b85f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -134,6 +134,7 @@ dmypy.json
 /*.ipynb
 /*.pkl
 /notebooks
+.pybryt_cache
 
 # ignore docs build
 /docs/html
diff --git a/demo/README.md b/demo/README.md
index 5c61a7c..f36a891 100644
--- a/demo/README.md
+++ b/demo/README.md
@@ -8,80 +8,3 @@ pip install pybryt
 
 and then launch the `index.ipynb` notebook in each of the directories under `demo` from Jupyter 
 Notebook, which demonstrates the process of using PyBryt to assess student submissions.
-
-## PyBryt is a pedagogical auto assessment library for Python. 
-
-
-The main goal of PyBryt as compared to other more conventional auto graders is to allow instructors to write more complex assignments that don't require students to follow a rigid structure for their solution.
-
-This allows learners to practice algorithm design, code design and solution implementation while receiving quick and meaningful pedagogical feedback.
-
-
-## Median Example 
-
-This first example is a somewhat simple one. In it, students are asked to implement a median function, and PyBryt is used to ensure that student solutions correctly implement the algorithm.
-In this notebook we have the reference implementation for the median function. A reference implementation is simply a solution that has been marked up with various annotations that assert the presence of different values and conditions on those values.
-
-In this example, we have an implementation of the median algorithm and a series of annotations that assert the presence of a few values. To check that students are computing values that are required to determine the actual value of the median.
-
-In this example, the first value we assert is that students should be sorting the list that they receive into the median function. We then see that they should be determining the length of that list in order to correctly compute the index at which the median lies in the sorted list.
-
-Finally, at the end of the notebook we see an annotation that asserts that the correct value, the value which we know in the test case, should be the median. Is found in memory. All these annotations come with success and failure messages, and these messages will be returned to students when they run PyBryt and also to the instructor when they run PyBryt as a means of providing meaningful feedback to the students.
-
-
-## Median Demo Submissions 
-
-Note that all the submissions in this demo returned the correct value for the test case and would pass the test of a conventional auto grading solution.
-
-In this example submission, we can see a student has imported NUMPY and returns the value of Np.median called on the input list.
-
-Because the assignment was for students to implement the algorithm themselves, this is not a valid solution, but it does return the correct value. An auto grader wouldn't be able to catch that. This is where PyBryt comes in. If we go and look at the output for this submission, we will see they receive a few messages that let them know that the instructor know that they weren't on the right track and are missing some key values that are needed to satisfy the reference.
-
-
-## Running PyBryt 
-
-Now let's run PyBryt. The process of running PyBryt is as follows. We first start by compiling a reference implementation, which is the notebook that I showed earlier. After we have compiled the reference information, we can save it to a file if needed, so we cannot reload it later without re executing the notebook or we go straight into grading
-
-## Assessment Process
-
-The process of grading is actually a two stage process.
-
-First, we start by generating a series of memory footprints which are encapsulated in the student implementation objects. To do this, simply executes the notebook or the student submission. With a trace function that records values that it observes in memory. Once we have these memory footprints.
-
-We can then use these and run them against the reference implementations.
-
-To check that they have, we see the right values in memory. Here we can see the results of running PyBryt against the submissions in the demo. If we look at submission 2, which is the one that imported NUMPY we can see a series of error messages that PyBryt was expecting to find certain values that were not included in the student’s submission. In this way we can tell that a student didn't implement the algorithm in good faith, and we know not to give credit to such submissions.
-
-
-## Fibonacci Demo 
-
-Let's look at a slightly more complex example. This example involves the use of multiple reference implementations.
-
-Here, students are going to be asked to implement a function that returns the NTH Fibonacci number, and which runs in linear time.
-
-In this reference implementation, we have two algorithms for determining the nth Fibonacci number. The first involves the use of a HashMap to remember past values, and the second involves the dynamic programming. We mark up each of these implementations by creating a series of value annotations and appending them to a list. We have two lists, one for the hash implementation and one for the dynamic programming implementation. As we run the test cases in this notebook, we populate these lists with annotations that assert the presence of the HashMap itself in various stages of being filled in for the HashMap implementation and the array of values needed to check the dynamic programming implementation. We also add a second kind of annotation called the time complexity annotation. This is PyBryt mechanism for asserting that a named block of student code runs with a specific runtime.
-
-In this example, we've asserted that it should run in linear time.
-
-Finally, we have a third reference implementation created. In this last reference implementation, will check to see that there are some markers of either of the acceptable implementations in the student’s memory footprint. In this way, we ensure that students are not implementing the naive algorithm, hence the failure message tide to that annotation.
-
-Finally, we create the reference implementation objects by passing the list to the reference implementation constructor along with the name for each reference implementation.
-
-
-## Fibonacci Demo Submissions
-
-Let's now let’s look at the results of running PyBryt against the submissions.
-The three submissions in this submission’s directory includes:
-
--	A HashMap implementation
--	A dynamic programming implementation
--	A naive implementation.
-
-We can see in these results that the HashMap implementation satisfied the HashMap reference and satisfied the reference concerning that the naive implementation was not being used. We see the dynamic programming satisfied its reference implementation and in the third example, which was the naive example, we see it failed all three references.
-
-
-## Conclusion 
-
-As you can see, PyBryt allows you to build complex assignments in such a way that students aren't forced to rigidly adhere to a set structure for their submission and is robust in the various failing of comparisons in conventional auto graders.
-For more information about PyBryt. You can visit the GitHub repository documentation and see try out the demos.
-
diff --git a/docs/annotations/relational_annotations.rst b/docs/annotations/relational_annotations.rst
index 17e2254..a40df3e 100644
--- a/docs/annotations/relational_annotations.rst
+++ b/docs/annotations/relational_annotations.rst
@@ -52,7 +52,7 @@ asserts that one annotation occurs before another:
         if n == 2:
             return fibs
 
-        for i in range(2, n):
+        for i in range(2, n-1):
             fibs[i] = fibs[i-1] + fibs[i-2]
 
             v = pybryt.Value(fibs) # array of first n Fibonacci numbers
diff --git a/pybryt/student.py b/pybryt/student.py
index db6dad2..6f85576 100644
--- a/pybryt/student.py
+++ b/pybryt/student.py
@@ -7,8 +7,10 @@ import dill
 import base64
 import nbformat
 import inspect
+import hashlib
 
 from contextlib import contextmanager
+from glob import glob
 from multiprocessing import Process, Queue
 from types import FrameType
 from typing import Any, Dict, List, NoReturn, Optional, Tuple, Union
@@ -18,7 +20,11 @@ from .execution import (
     tracing_on, TRACING_VARNAME
 )
 from .reference import generate_report, ReferenceImplementation, ReferenceResult
-from .utils import Serializable
+from .utils import pickle_and_hash, Serializable
+
+
+CACHE_DIR_NAME = ".pybryt_cache"
+_CACHE_STUDENT_IMPL_PREFIX = "student_impl_{}.pkl"
 
 
 class StudentImplementation(Serializable):
@@ -93,6 +99,62 @@ class StudentImplementation(Serializable):
         stu.values = footprint
         return stu
 
+    @classmethod
+    def combine(cls, impls: List['StudentImplementation']) -> 'StudentImplementation':
+        """
+        Combine a series of student implementations into a single student implementation.
+
+        Collects the memory footprint of each implementation into a single list and offsets the
+        timestamp of each object by the total number of steps for each preceding student
+        implementation in the list. 
+
+        Assumes that the student implementations are provided in sorted order. Filters out duplicate
+        values present in multiple implementations by keeping the earliest.
+
+        Args:
+            impls (``list[StudentImplementation]``): the list of implementations to combine
+
+        Returns:
+            ``StudentImplementation``: the combined implementation
+        """
+        new_mfp = []  # the new memory footprint
+        seen = set()  # set to track which values we've seen
+        timestamp_offset = 0  # offset for timestamps in the new memory footprint
+        for impl in impls:
+            for obj, ts in impl.values:
+                h = pickle_and_hash(obj)
+                if h not in seen:
+                    ts += timestamp_offset
+                    new_mfp.append((obj, ts))
+                    seen.add(h)
+            timestamp_offset += impl.steps
+        return cls.from_footprint(new_mfp, timestamp_offset)
+
+    @classmethod
+    def from_cache(cls, cache_dir=CACHE_DIR_NAME, combine=True) -> \
+            Union['StudentImplementation', List['StudentImplementation']]:
+        """
+        Load one or more student implementations from a cache.
+
+        All files are combined into a single student implementation by default, but a list can be
+        returned instead by setting ``combine=False``.
+
+        Args:
+            cache_dir (``str``, optional): the path to the cache directory
+            combine (``bool``, optional): whether to combine the implementations
+
+        Returns:
+            ``StudentImplementation`` or ``list[StudentImplementation]``: the student implementations
+            loaded from the cache.
+        """
+        impls = []
+        for impl_path in glob(os.path.join(cache_dir, _CACHE_STUDENT_IMPL_PREFIX.format("*"))):
+            impls.append(cls.load(impl_path))
+        if combine:
+            return cls.combine(impls)
+        else:
+            return impls
+
     def __eq__(self, other: Any) -> bool:
         """
         Checks whether a student implementation is equal to another object.
@@ -247,12 +309,15 @@ class check:
     _observed: Optional[List[Tuple[Any, int]]]
     """the memory footprint"""
 
+    _cache: bool
+    """whether to cache the memory footprint and results"""
+
     _kwargs: Dict[str, Any]
     """keyword arguments passed to ``pybryt.execution.create_collector``"""
 
     def __init__(
         self, ref: Union[str, ReferenceImplementation, List[str], List[ReferenceImplementation]], 
-        report_on_error: bool = True, show_only: Optional[str] = None, **kwargs
+        report_on_error: bool = True, show_only: Optional[str] = None, cache: bool = True, **kwargs
     ):
         if isinstance(ref, str):
             ref = ReferenceImplementation.load(ref)
@@ -274,6 +339,29 @@ class check:
         self._frame = None
         self._observed = None
         self._report_on_error = report_on_error
+        self._cache = cache
+
+    def _cache_check(self, stu, res):
+        """
+        Cache the student implementation and reference results in the PyBryt cache directory.
+
+        Args:
+            stu (``StudentImplementation``): the student implementation created by the check
+            res (``Union[ReferenceImplementation, list[ReferenceImplementation]]``): the reference 
+                results
+        """
+        os.makedirs(CACHE_DIR_NAME, exist_ok=True)  # create cache directory if needed
+
+        if not isinstance(res, list):
+            res = [res]
+
+        for r in res:
+            res_path = os.path.join(CACHE_DIR_NAME, f"{r.name}_results.pkl")
+            r.dump(res_path)
+
+        ref_hash = hashlib.sha1("".join(r.name for r in res).encode()).hexdigest()
+        stu_path = os.path.join(CACHE_DIR_NAME, _CACHE_STUDENT_IMPL_PREFIX.format(ref_hash))
+        stu.dump(stu_path)
 
     def __enter__(self):
         if _get_tracing_frame() is not None:
@@ -299,6 +387,9 @@ class check:
                 if report:
                     print(report)
 
+                if self._cache:
+                    self._cache_check(stu, res)
+
         return False
 
 


Test patch:
diff --git a/tests/test_student.py b/tests/test_student.py
index 438507e..fcb01ec 100644
--- a/tests/test_student.py
+++ b/tests/test_student.py
@@ -6,6 +6,7 @@ import nbformat
 import pytest
 import pkg_resources
 
+from copy import deepcopy
 from functools import lru_cache
 from textwrap import dedent
 from types import MethodType
@@ -118,66 +119,119 @@ def test_check_cm(capsys):
     _, stu = generate_impl()
     mfp = stu.values
 
-    with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
-        check_cm = check(ref)
-        with check_cm:
-            check_cm._observed = mfp
-
-    captured = capsys.readouterr()
-    expected = dedent("""\
-        REFERENCE: foo
-        SATISFIED: True
-        MESSAGES:
-          - SUCCESS: Sorted the sample correctly
-          - SUCCESS: Computed the size of the sample
-          - SUCCESS: computed the correct median
-    """)
-    assert captured.out == expected
+    with mock.patch.object(check, "_cache_check") as mocked_cache:
+        with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
+            check_cm = check(ref, cache=False)
+            with check_cm:
+                check_cm._observed = mfp
+
+            mocked_cache.assert_not_called()
+
+        captured = capsys.readouterr()
+        expected = dedent("""\
+            REFERENCE: foo
+            SATISFIED: True
+            MESSAGES:
+              - SUCCESS: Sorted the sample correctly
+              - SUCCESS: Computed the size of the sample
+              - SUCCESS: computed the correct median
+        """)
+        assert captured.out == expected
 
-    with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
-        ref_filename = pkg_resources.resource_filename(__name__, os.path.join("files", "expected_ref.pkl"))
-        check_cm = check(ref_filename)
-        with check_cm:
-            check_cm._observed = mfp
-
-        check_cm2 = check([ref_filename])
-        assert check_cm._ref == check_cm2._ref
-
-    captured = capsys.readouterr()
-    expected = dedent("""\
-        REFERENCE: foo
-        SATISFIED: True
-        MESSAGES:
-          - SUCCESS: Sorted the sample correctly
-          - SUCCESS: Computed the size of the sample
-          - SUCCESS: computed the correct median
-    """)
-    assert captured.out == expected
-
-    # check no action when tracing
-    global __PYBRYT_TRACING__
-    __PYBRYT_TRACING__ = True
-
-    try:
         with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
+            ref_filename = pkg_resources.resource_filename(__name__, os.path.join("files", "expected_ref.pkl"))
+            check_cm = check(ref_filename)
+            with check_cm:
+                check_cm._observed = mfp
+
+            mocked_cache.assert_called()
+
+            check_cm2 = check([ref_filename])
+            assert check_cm._ref == check_cm2._ref
+
+        captured = capsys.readouterr()
+        expected = dedent("""\
+            REFERENCE: foo
+            SATISFIED: True
+            MESSAGES:
+              - SUCCESS: Sorted the sample correctly
+              - SUCCESS: Computed the size of the sample
+              - SUCCESS: computed the correct median
+        """)
+        assert captured.out == expected
+
+        # check no action when tracing
+        global __PYBRYT_TRACING__
+        __PYBRYT_TRACING__ = True
+
+        try:
+            with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
+                check_cm = check(ref)
+                with check_cm:
+                    pass
+
+                mocked_tracing.assert_not_called()
+
+        except:
+            __PYBRYT_TRACING__ = False
+            raise
+
+        else:
+            __PYBRYT_TRACING__ = False
+
+        # test errors
+        with pytest.raises(ValueError, match="Cannot check against an empty list of references"):
+            check([])
+
+        with pytest.raises(TypeError, match="Invalid values in the reference list"):
+            check([ref, "path", 1])
+
+    # check caching
+    with mock.patch("pybryt.student.tracing_on") as mocked_tracing, mock.patch("pybryt.student.tracing_off"):
+        with mock.patch("pybryt.student.StudentImplementation") as mocked_stu, \
+                mock.patch("pybryt.student.generate_report") as mocked_generate, \
+                mock.patch("pybryt.student.os.makedirs") as mocked_makedirs:
+            mocked_stu.from_footprint.return_value.check.return_value = [mock.MagicMock()]
+            mocked_stu.from_footprint.return_value.check.return_value[0].name = "foo"
+            # breakpoint()
             check_cm = check(ref)
             with check_cm:
-                pass
-            mocked_tracing.assert_not_called()
+                check_cm._observed = mfp
+            
+            mocked_makedirs.assert_called_with(".pybryt_cache", exist_ok=True)
+            mocked_stu.from_footprint.return_value.dump.assert_called()
+            mocked_stu.from_footprint.return_value.check.return_value[0].dump.assert_called_with(".pybryt_cache/foo_results.pkl")
 
-    except:
-        __PYBRYT_TRACING__ = False
-        raise
 
-    else:
-        __PYBRYT_TRACING__ = False
+def test_from_cache():
+    """
+    """
+    with mock.patch("pybryt.student.glob") as mocked_glob, \
+            mock.patch.object(StudentImplementation, "load") as mocked_load, \
+            mock.patch.object(StudentImplementation, "combine") as mocked_combine:
+        mocked_glob.return_value = [".pybryt_cache/student_impl_foo.pkl", ".pybryt_cache/student_impl_bar.pkl"]
+        StudentImplementation.from_cache(combine=False)
 
-    # test errors
-    with pytest.raises(ValueError, match="Cannot check against an empty list of references"):
-        check([])
+        mocked_load.assert_has_calls([mock.call(fp) for fp in mocked_glob.return_value])
+        mocked_combine.assert_not_called()
 
-    with pytest.raises(TypeError, match="Invalid values in the reference list"):
-        check([ref, "path", 1])
+        StudentImplementation.from_cache()
+
+        mocked_combine.assert_called()
+
+
+def test_combine():
+    """
+    """
+    _, stu = generate_impl()
+    stu2 = deepcopy(stu)
+    stu2.steps += 1
+    stu2.values.append(([1, 2, 3, 4], stu2.steps))
+
+    comb = StudentImplementation.combine([stu, stu2])
+    assert len(comb.values) == len(stu.values)  + 1
+    assert comb.steps == stu.steps + stu2.steps
+    assert comb.values[-1][1] == stu.steps + stu2.steps
 
 
 def test_generate_student_impls():