MTG Search Engine

A search engine based on Scryfall, written in C, with a NextJS frontend. You can see the website on monarch.djpiper28.co.uk. The source code is available on Github.

A Brief Overview of How It Works

Interpreting User Input

The parser is written as a PEG and generated with packcc. An abstract syntax tree is created during the parse of the input string. After this the tree is then optimised, and interpreted. Below is a diagram of the process. (The diagram is also available as a drawio diagram).

The above example generates two sets to start with: the set of all cards printed in M19, and the set of all cards that are legal in commander. The "and" operator preforms a set intersection, generating a third set. The regex of cards matching /goblin .*/ is then performed on each card in the intersection set.

Indexes

There are a lot of indexes generated to make lookups faster. Many set generators, such as "power>5", are O(1) complexity. A "normal" index is a balanced binary tree (implemented as AVL trees) that stores the data in order. For the power of a magic card, this allows for one index for all operators (>, < >=, <=, =, :).

Some indexes are a bit different, for example, the "set:m19" index is a pre-computed set of all cards printed in M19. Another special index type is a trie tree for textual lookups (i.e: "name:goblin").

Most things that can be pre-computed are, leading to about 2.4GiB of memory usage (this number will probably change). For things that cannot be pre-computed, namely regex lookups, optimisations are used to allow the regex matching to be executed against as few cards as possible.

Other Cool Technical Things

Quite a lot of the code is to make the application multi-threaded, implemented as a light-thread system where tasks are submitted to a task queue that is consumed by threads in a pool. The web server that is used to serve data to the frontend uses an async pattern, the job is submitted to the task pool and the server thread polls for completion on all pending queries.

The hosted environment is self-hosted by me and runs in my Kubernetes cluster, and has its cards updated weekly. The search engine is also embeddable and can be used in other projects as a library. The hosted version has a Go API client, and an Open API definition so it can be used in your projects if you want to.

There is a lot of testing setup for the project, about 80% coverage, with unit tests, system tests, memory tests, and integration tests.