I want to create a script that makes sure contributors in my project are rebasing their changes before merging, rather than merging first from the target branch before then merging their changes back.

I could banish all merge commits from merge request branches, but merge commits are still useful (for example, a mega-branch that has incorporated several smaller merge requests, to be merged into the main branch). Allowing merge commits also creates a situation where a contributor could merge a small branch that has a merge commit containing changes from the main branch, and so on.

If I have two branches, branch/feature and main, how can I walk the commit graph to be sure that it's a proper tree, all the way down to the proposed merge base?

I tried going through the commits and parsing the merge messages themselves, but those can easily be edited. I'm trying to figure out a solution that traverses the graph itself.