Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Detect cycle during projectivize #10877

Merged
merged 20 commits into from
Jun 8, 2022
Merged

Detect cycle during projectivize #10877

merged 20 commits into from
Jun 8, 2022

Commits on May 30, 2022

  1. detect cycle during projectivize

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    b776039 View commit details
    Browse the repository at this point in the history

  2. not complete test to detect cycle in projectivize

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    c4e404e View commit details
    Browse the repository at this point in the history

  3. boolean to int type to propagate error

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    a7aa8fb View commit details
    Browse the repository at this point in the history

  4. use unordered_set instead of set

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    794567e View commit details
    Browse the repository at this point in the history

  5. moved error message to errors

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    4adb3fc View commit details
    Browse the repository at this point in the history

  6. removed cycle from test case

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    8b92612 View commit details
    Browse the repository at this point in the history

  7. use find instead of count

    @kadarakos
    kadarakos committed May 30, 2022
    Configuration menu
    Copy the full SHA
    c5763f1 View commit details
    Browse the repository at this point in the history

Commits on May 31, 2022

  1. cycle check: only perform one lookup

    @danieldk
    danieldk committed May 31, 2022
    Configuration menu
    Copy the full SHA
    70433ce View commit details
    Browse the repository at this point in the history

  2. Return bool again from _has_head_as_ancestor 

    Communicate presence of cycles through an output argument.
    @danieldk
    danieldk committed May 31, 2022
    Configuration menu
    Copy the full SHA
    a96716f View commit details
    Browse the repository at this point in the history

Commits on Jun 1, 2022

  1. Switch to returning std::pair to encode presence of a cycle 

    The has_cycle pointer is too easy to misuse. Ideally, we would have a
sum type like Rust's `Result` here, but C   is not there yet.
    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    cfbedf3 View commit details
    Browse the repository at this point in the history

  2. _is_non_proj_arc: clarify what we are returning

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    10eacfd View commit details
    Browse the repository at this point in the history

  3. _has_head_as_ancestor: remove count 

    We are now explicitly checking for cycles, so the algorithm must always
terminate. Either we encounter the head, we find a root, or a cycle.
    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    0f6a2a6 View commit details
    Browse the repository at this point in the history

  4. _is_nonproj_arc: simplify condition

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    a299a6c View commit details
    Browse the repository at this point in the history

  5. Another refactor using C exceptions

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    b60b714 View commit details
    Browse the repository at this point in the history

  6. Remove unused error code

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    0b7ca4c View commit details
    Browse the repository at this point in the history

  7. Print graph with cycle on exception

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    31b3857 View commit details
    Browse the repository at this point in the history

  8. Include .hh files in source package

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    ed61b86 View commit details
    Browse the repository at this point in the history

  9. Add FIXME comment

    @danieldk
    danieldk committed Jun 1, 2022
    Configuration menu
    Copy the full SHA
    08e017c View commit details
    Browse the repository at this point in the history

Commits on Jun 6, 2022

  1. cycle detection test

    @kadarakos
    kadarakos committed Jun 6, 2022
    Configuration menu
    Copy the full SHA
    87f8005 View commit details
    Browse the repository at this point in the history

Commits on Jun 7, 2022

  1. find cycle when starting from problematic vertex

    @kadarakos
    kadarakos committed Jun 7, 2022
    Configuration menu
    Copy the full SHA
    dadb55a View commit details
    Browse the repository at this point in the history