jbaiter / python-rust-fst Goto Github PK

Python bindings for Rust's fst crate

License: MIT License

Python 56.96% Rust 30.54% Batchfile 1.08% Shell 2.76% C 8.65%

python-rust-fst's Introduction

python-rust-fst

Python bindings for burntsushi's fst crate (rustdocs) for FST-backed sets and maps.

For reasons why you might want to consider using it, see BurntSushi's great article on "Index[ing] 1,600,000,000 Keys with Automata and Rust".

tl;dr:

Work with larger-than-memory sets
Perform fuzzy search using Levenshtein automata

Installation

rust_fst is available as a binary wheel for the most common platforms (Linux 64bit x86, Windows 32/64bit x86 and OSX 64bit x86) and thus does not require a Rust installation.

Just run pip install rust_fst to install the latest stable version of the package.

Development

You will need:
- Python >= 3.3, Python or PyPy >= 2.7 with development headers installed
- Rust nightly (install via rustup)
Run rustup override add nightly to add an override for rustup to use the nightly channel for the repository
Install with pip (without the -e flag, it does not work!)
Run tests with py.test python-rust-fst/tests and make sure you are not in the root of the repo, since the installed (and compiled) package will not be used in that case.

Status

The package exposes almost all functionality of the fst crate, except for:

Combining the results of slicing, search and search_re with set operations
Using raw transducers

Examples

from rust_fst import Map, Set

# Building a set in memory
keys = ["fa", "fo", "fob", "focus", "foo", "food", "foul"]
s = Set.from_iter(keys)

# Fuzzy searches on the set
matches = list(s.search(term="foo", max_dist=1))
assert matches == ["fo", "fob", "foo", "food"]

# Searching with a regular expression
matches = list(s.search_re(r'f\w{2}'))
assert matches == ["fob", "foo"]

# Store map on disk, requiring only constant memory for querying
items = [("bruce", 1), ("clarence", 2), ("stevie", 3)]
m = Map.from_iter(items, path="/tmp/map.fst")

# Find all items whose key is greater or equal (in lexicographical sense) to
# 'clarence'
matches = dict(m['clarence':])
assert matches == {'clarence': 2, 'stevie': 3}

# Create a map from a file input, using generators/yield
# The input file must be sorted on the first column, and look roughly like
#   keyA 123
#   keyB 456
def file_iterator(fpath):
  with open(fpath, 'rt') as fp:
    for line in fp:
      key, value = line.strip().split()
      yield key, int(value)
m = Map.from_iter( file_iterator('/your/input/file/'), '/your/mmapped/output.fst')

# re-open a file you built previously with from_iter()
m = Map(path='/path/to/existing.fst')

Documentation

Head over to readthedocs.org for the API documentation.

If you want to know more about performance characteristics, memory usage and about the implementation details, please head over to the documentation for the Rust crate

python-rust-fst's People

Contributors

Stargazers

Watchers

Forkers

pombredanne stephica pothix davidblewett kthwaite isabella232

python-rust-fst's Issues

Don't segfault on panics

Also, the Python interpreter should not be segfaulting. The ffi layer should be catching panics and converting them to aborts. Otherwise it is UB.
BurntSushi/fst#57 (comment)

Fatal Runtime Error when Iterating over Set Union

% RUST_BACKTRACE=1 python -c 'from rust_fst import Set; it = Set.from_iter(["a", "b"]).union(Set.from_iter([])); list(it)'       
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: NulError(0, [0])', ../src/libcore/result.rs:785
stack backtrace:
   1:     0x7fd6c57049d0 - std::sys::backtrace::tracing::imp::write::h9fb600083204ae7f
   2:     0x7fd6c57125eb - std::panicking::default_hook::_$u7b$$u7b$closure$u7d$$u7d$::hca543c34f11229ac
   3:     0x7fd6c5712223 - std::panicking::default_hook::hc2c969e7453d080c
   4:     0x7fd6c56d7b78 - std::panicking::rust_panic_with_hook::hfe203e3083c2b544
   5:     0x7fd6c5712831 - std::panicking::begin_panic::h4889569716505182
   6:     0x7fd6c56d9d8a - std::panicking::begin_panic_fmt::h484cd47786497f03
   7:     0x7fd6c57127ce - rust_begin_unwind
   8:     0x7fd6c572627f - core::panicking::panic_fmt::h257ceb0aa351d801
   9:     0x7fd6c5689ebe - core::result::unwrap_failed::h6b97717ae28838df
  10:     0x7fd6c5699c11 - fst_set_union_next
  11:     0x7fd6c59e7def - ffi_call_unix64
                        at ../src/x86/unix64.S:76
  12:     0x7fd6c59e7857 - ffi_call
                        at ../src/x86/ffi64.c:525
  13:     0x7fd6c5c05d63 - cdata_call
                        at c/_cffi_backend.c:3025
  14:           0x459892 - _PyObject_FastCallDict
  15:           0x54f116 - <unknown>
  16:           0x553aae - _PyEval_EvalFrameDefault
  17:           0x54e4c7 - <unknown>
  18:           0x5582c1 - _PyFunction_FastCallDict
  19:           0x459c10 - _PyObject_Call_Prepend
  20:           0x459892 - _PyObject_FastCallDict
  21:           0x4e2713 - <unknown>
  22:           0x4915bc - <unknown>
  23:           0x491a68 - <unknown>
  24:           0x4da8d6 - <unknown>
  25:           0x459892 - _PyObject_FastCallDict
  26:           0x54f116 - <unknown>
  27:           0x553aae - _PyEval_EvalFrameDefault
  28:           0x54efc0 - <unknown>
  29:           0x54ff72 - PyEval_EvalCode
  30:           0x42c379 - PyRun_SimpleStringFlags
  31:           0x441177 - Py_Main
  32:           0x421f63 - main
  33:     0x7fd6c61de1c0 - __libc_start_main
  34:           0x422019 - _start
  35:                0x0 - <unknown>
fatal runtime error: failed to initiate panic, error 5
zsh: abort (core dumped)  RUST_BACKTRACE=1 python -c

Efficient range operations over multiple Set objects

I am building an application that generates new FST objects every hour. I would like to be able to do efficient range operations over a group of these FST files. Conceptually, something like combining the __getitem__ implementation with the OpBuilder. Basically, returning a KeyStreamIterator for multiple Set objects' range operation (pseudo code:

 s1 = Set.from_iter(["bar", "baz", "foo", "moo"])
 s2 = Set.from_iter(["bing", "jar, "foo", "moo"])
 s2 = Set.from_iter(["bap", "bonk, "foo", "moo"])
(s1 + s2 + s3)["b":"f"]

The existing API seems cumbersome for doing operations across multiple. You have to pick a (possibly arbitrary) instance, then call .union / .intersection etc with the rest of the objects. Would it be possible to have some sort of MultiSet class that could perform efficient calls across multiple Set objects?

I can take a crack at implementing it; it appears the underlying Rust API would support this.

Upstream file version changed

It appears the on-disk version of an FST file changed since the last release of this package:

In [1]: import rust_fst

In [2]: fst_map = rust_fst.Map('output.fst')
---------------------------------------------------------------------------
TransducerError                           Traceback (most recent call last)
<ipython-input-2-5569acb18f20> in <module>()
----> 1 fst_map = rust_fst.Map('output.fst')

~/.virtualenvs/proc_lookup/lib/python3.6/site-packages/rust_fst/map.py in __init__(self, path, _pointer)
    174         if path:
    175             s = checked_call(lib.fst_map_open, self._ctx,
--> 176                              ffi.new("char[]", path.encode('utf8')))
    177         else:
    178             s = _pointer

~/.virtualenvs/proc_lookup/lib/python3.6/site-packages/rust_fst/lib.py in checked_call(fn, ctx, *args)
     67     if err_type is None:
     68         err_type = FstError
---> 69     raise err_type(msg)

TransducerError: Error opening FST: expected API version 1, got API version 2. It looks like the FST you're trying to open is either not an FST file or it was generated with a different version of the 'fst' crate. You'll either need to change the version of the 'fst' crate you're using, or re-generate the FST.

I tried building the package locally using the latest nightly Rust, but got this:

In [1]: import rust_fst

In [2]: fst_map = rust_fst.Map('output.fst')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-2-5569acb18f20> in <module>()
----> 1 fst_map = rust_fst.Map('output.fst')

~/.virtualenvs/proc_lookup/lib/python3.6/site-packages/rust_fst/map.py in __init__(self, path, _pointer)
    174         if path:
    175             s = checked_call(lib.fst_map_open, self._ctx,
--> 176                              ffi.new("char[]", path.encode('utf8')))
    177         else:
    178             s = _pointer

~/.virtualenvs/proc_lookup/lib/python3.6/site-packages/rust_fst/lib.py in checked_call(fn, ctx, *args)
     55 def checked_call(fn, ctx, *args):
     56     res = fn(ctx, *args)
---> 57     if not ctx.has_error:
     58         return res
     59     type_str = ffi.string(ctx.error_type).decode('utf8')

ValueError: got a _Bool of value 80, expected 0 or 1

Also, in order to build it, I had to do rustup default nightly && pip install --no-cache-dir . && rustup default stable because it appears pip copies the code to /tmp before building, so the rustup override didn't work. I built with: rustc 1.24.0-nightly (687d3d15b 2018-01-02).

ModuleNotFoundError rust_setuptools using new pip version 20.0.1

After upgrading my pip dependency to 20.0.1, I am getting ModuleNotFoundError while installing rust_fst using pip.

> pip --version                                                                                                 
pip 20.0.1 from /Users/anjch/opt/anaconda3/lib/python3.7/site-packages/pip (python 3.7)

> pip install rust_fst                                                                                                
Collecting rust_fst
  Downloading rust-fst-0.1.2.tar.gz (8.3 kB)
    ERROR: Command errored out with exit status 1:
     command: /Users/anjch/opt/anaconda3/bin/python -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/private/var/folders/pr/0265q6nd5gd6gf9k0f8shxycv008rp/T/pip-install-yzk_xmqs/rust-fst/setup.py'"'"'; __file__='"'"'/private/var/folders/pr/0265q6nd5gd6gf9k0f8shxycv008rp/T/pip-install-yzk_xmqs/rust-fst/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' egg_info --egg-base /private/var/folders/pr/0265q6nd5gd6gf9k0f8shxycv008rp/T/pip-install-yzk_xmqs/rust-fst/pip-egg-info
         cwd: /private/var/folders/pr/0265q6nd5gd6gf9k0f8shxycv008rp/T/pip-install-yzk_xmqs/rust-fst/
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/private/var/folders/pr/0265q6nd5gd6gf9k0f8shxycv008rp/T/pip-install-yzk_xmqs/rust-fst/setup.py", line 3, in <module>
        from rust_setuptools import (build_rust_cmdclass, build_install_lib_cmdclass,
    ModuleNotFoundError: No module named 'rust_setuptools'
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

However, the installation succeeds using older version of pip v 19.3

> pip --version                                                                                               
pip 19.3.1 from /Users/anjch/opt/anaconda3/envs/aws/lib/python3.8/site-packages/pip (python 3.8)
> pip install rust_fst                                                                                              
Collecting rust_fst
  Downloading https://files.pythonhosted.org/packages/23/12/42db4ee067877f1a9be3f4f2c1c70499036c45ab2dd0abb44b329ee66756/rust_fst-0.1.2-py2.py3-none-macosx_10_9_x86_64.whl (858kB)
     |████████████████████████████████| 860kB 863kB/s
Requirement already satisfied: cffi>=1.0.0 in ./opt/anaconda3/envs/aws/lib/python3.8/site-packages (from rust_fst) (1.13.2)
Requirement already satisfied: pycparser in ./opt/anaconda3/envs/aws/lib/python3.8/site-packages (from cffi>=1.0.0->rust_fst) (2.19)
Installing collected packages: rust-fst
Successfully installed rust-fst-0.1.2

Consider using Armin's snaek library

Armin Ronacher has factored out the necessary bits of building wheels that use Rust, but do not need to link to libpython into a library called snaek: https://github.com/mitsuhiko/snaek . It might be a better alternative than carrying that maintenance burden here.

manypython wheels segfault on i686

On i686 systems with the manypython wheel installed the tests cause a segmentation fault, the location of which differs between build targets:

With release: On fst_{file,mem}setbuilder_insert
With debug: On fst_set_opbuilder_{union,difference,intersection,symmetric_difference}

This only happens when the wheel was built inside of the manypython-i686 docker environment. I successfully compiled and ran the tests under Ubuntu 12.04 in a i686 VM.

Free before GC

I noticed this comment: https://github.com/jbaiter/python-rust-fst/blob/master/rust_fst/common.py#L20

    # TODO: We could safely free the structures before the GC does,
    #       but unfortunately removing GC-callbacks is only supported
    #       in cffi >= 1.7, which is not yet released.

The current version of cffi is 1.11.2. I don't know what versions PyPy is shipping with now however.