Rewrite fzf in Go

32 files changed, 3464 insertions, 47 deletions

diff --git a/.gitignore b/.gitignore
index 1627430d..09154676 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
+bin
+src/fzf/fzf_*
 pkg
 Gemfile.lock
 .DS_Store
diff --git a/install b/install
index 3176b27d..6b64a3f2 100755
--- a/install
+++ b/install
@@ -3,60 +3,81 @@
 cd `dirname $BASH_SOURCE`
 fzf_base=`pwd`
 
-# ruby executable
-echo -n "Checking Ruby executable ... "
-ruby=`which ruby`
-if [ $? -ne 0 ]; then
-  echo "ruby executable not found!"
-  exit 1
-fi
-
-# System ruby is preferred
-system_ruby=/usr/bin/ruby
-if [ -x $system_ruby -a $system_ruby != "$ruby" ]; then
-  $system_ruby --disable-gems -rcurses -e0 2> /dev/null
-  [ $? -eq 0 ] && ruby=$system_ruby
-fi
-
-echo "OK ($ruby)"
+ARCHI=$(uname -sm)
 
-# Curses-support
-echo -n "Checking Curses support ... "
-"$ruby" -rcurses -e0 2> /dev/null
-if [ $? -eq 0 ]; then
-  echo "OK"
-else
-  echo "Not found"
-  echo "Installing 'curses' gem ... "
-  if (( EUID )); then
-    /usr/bin/env gem install curses --user-install
+download() {
+  echo "Downloading fzf executable ($1) ..."
+  if curl -fLo "$fzf_base"/bin/fzf https://github.com/junegunn/fzf-bin/releases/download/snapshot/$1; then
+    chmod +x "$fzf_base"/bin/fzf
   else
-    /usr/bin/env gem install curses
+    echo "Failed to download $1"
+    exit 1
   fi
+}
+
+mkdir -p "$fzf_base"/bin
+if [ "$ARCHI" = "Darwin x86_64" ]; then
+  download fzf_darwin_amd64
+elif [ "$ARCHI" = "Linux x86_64" ]; then
+  download fzf_linux_amd64
+else # No prebuilt executable
+  echo "No prebuilt binary for $ARCHI ... Installing legacy Ruby version ..."
+
+  # ruby executable
+  echo -n "Checking Ruby executable ... "
+  ruby=`which ruby`
   if [ $? -ne 0 ]; then
-    echo
-    echo "Failed to install 'curses' gem."
-    if [[ $(uname -r) =~ 'ARCH' ]]; then
-      echo "Make sure that base-devel package group is installed."
-    fi
+    echo "ruby executable not found!"
     exit 1
   fi
-fi
 
-# Ruby version
-echo -n "Checking Ruby version ... "
-"$ruby" -e 'exit RUBY_VERSION >= "1.9"'
-if [ $? -eq 0 ]; then
-  echo ">= 1.9"
-  "$ruby" --disable-gems -rcurses -e0 2> /dev/null
+  # System ruby is preferred
+  system_ruby=/usr/bin/ruby
+  if [ -x $system_ruby -a $system_ruby != "$ruby" ]; then
+    $system_ruby --disable-gems -rcurses -e0 2> /dev/null
+    [ $? -eq 0 ] && ruby=$system_ruby
+  fi
+
+  echo "OK ($ruby)"
+
+  # Curses-support
+  echo -n "Checking Curses support ... "
+  "$ruby" -rcurses -e0 2> /dev/null
+  if [ $? -eq 0 ]; then
+    echo "OK"
+  else
+    echo "Not found"
+    echo "Installing 'curses' gem ... "
+    if (( EUID )); then
+      /usr/bin/env gem install curses --user-install
+    else
+      /usr/bin/env gem install curses
+    fi
+    if [ $? -ne 0 ]; then
+      echo
+      echo "Failed to install 'curses' gem."
+      if [[ $(uname -r) =~ 'ARCH' ]]; then
+        echo "Make sure that base-devel package group is installed."
+      fi
+      exit 1
+    fi
+  fi
+
+  # Ruby version
+  echo -n "Checking Ruby version ... "
+  "$ruby" -e 'exit RUBY_VERSION >= "1.9"'
   if [ $? -eq 0 ]; then
-    fzf_cmd="$ruby --disable-gems $fzf_base/fzf"
+    echo ">= 1.9"
+    "$ruby" --disable-gems -rcurses -e0 2> /dev/null
+    if [ $? -eq 0 ]; then
+      fzf_cmd="$ruby --disable-gems $fzf_base/fzf"
+    else
+      fzf_cmd="$ruby $fzf_base/fzf"
+    fi
   else
+    echo "< 1.9"
     fzf_cmd="$ruby $fzf_base/fzf"
   fi
-else
-  echo "< 1.9"
-  fzf_cmd="$ruby $fzf_base/fzf"
 fi
 
 # Auto-completion
@@ -85,10 +106,17 @@ for shell in bash zsh; do
 # Setup fzf function
 # ------------------
 unalias fzf 2> /dev/null
-fzf() {
-  $fzf_cmd "\$@"
-}
-export -f fzf > /dev/null
+unset fzf 2> /dev/null
+if [ -x "$fzf_base/bin/fzf" ]; then
+  if [[ ! "\$PATH" =~ "$fzf_base/bin" ]]; then
+    export PATH="$fzf_base/bin:\$PATH"
+  fi
+else
+  fzf() {
+    $fzf_cmd "\$@"
+  }
+  export -f fzf > /dev/null
+fi
 
 # Auto-completion
 # ---------------
diff --git a/src/Dockerfile b/src/Dockerfile
new file mode 100644
index 00000000..3c062eea
--- /dev/null
+++ b/src/Dockerfile
@@ -0,0 +1,33 @@
+FROM ubuntu:14.04
+MAINTAINER Junegunn Choi <junegunn.c@gmail.com>
+
+# apt-get
+RUN apt-get update && apt-get -y upgrade
+RUN apt-get install -y --force-yes git vim-nox curl procps sudo \
+                                   build-essential libncurses-dev
+
+# Setup jg user with sudo privilege
+RUN useradd -s /bin/bash -m jg && echo 'jg:jg' | chpasswd && \
+    echo 'jg ALL=(ALL) NOPASSWD: ALL' > /etc/sudoers.d/jg
+
+# Setup dotfiles
+USER jg
+RUN cd ~ && git clone https://github.com/junegunn/dotfiles.git && \
+    dotfiles/install > /dev/null
+
+# Install Go 1.4
+RUN cd ~ && curl https://storage.googleapis.com/golang/go1.4.linux-amd64.tar.gz | tar -xz && \
+    mv go go1.4 && \
+    echo 'export GOROOT=~/go1.4' >> ~/dotfiles/bashrc-extra && \
+    echo 'export PATH=~/go1.4/bin:$PATH' >> ~/dotfiles/bashrc-extra
+
+# Symlink fzf directory
+RUN mkdir -p ~jg/go/src/github.com/junegunn && \
+    ln -s /fzf ~jg/go/src/github.com/junegunn/fzf
+
+# Volume
+VOLUME /fzf
+
+# Default CMD
+CMD cd ~jg/go/src/github.com/junegunn/fzf/src && /bin/bash -l
+
diff --git a/src/LICENSE b/src/LICENSE
new file mode 100644
index 00000000..fe4c31ae
--- /dev/null
+++ b/src/LICENSE
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2015 Junegunn Choi
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/src/Makefile b/src/Makefile
new file mode 100644
index 00000000..bae4c906
--- /dev/null
+++ b/src/Makefile
@@ -0,0 +1,49 @@
+BINARY := fzf/fzf
+
+UNAME_S := $(shell uname -s)
+ifeq ($(UNAME_S),Darwin)
+	BINARY := $(BINARY)_darwin
+else ifeq ($(UNAME_S),Linux)
+	BINARY := $(BINARY)_linux
+endif
+
+UNAME_M := $(shell uname -m)
+ifneq ($(filter i386 i686,$(UNAME_M)),)
+$(error "filtered is not supported, yet.")
+endif
+
+ifeq ($(UNAME_M),x86_64)
+	BINARY := $(BINARY)_amd64
+else ifneq ($(filter i386 i686,$(UNAME_M)),)
+	BINARY := $(BINARY)_386
+else # TODO
+$(error "$(UNAME_M) is not supported, yet.")
+endif
+
+BINDIR  = ../bin
+SOURCES = $(wildcard *.go fzf/*.go)
+
+all: build
+
+build: $(BINARY)
+
+$(BINARY): $(SOURCES)
+	go get
+	go test -v
+	cd fzf && go build -o $(notdir $(BINARY))
+
+install: $(BINARY)
+	mkdir -p $(BINDIR)
+	cp -f $(BINARY) $(BINDIR)/fzf
+
+clean:
+	rm -f $(BINARY)
+
+docker:
+	docker build -t junegunn/ubuntu-sandbox .
+
+linux64:
+	docker run -i -t -u jg -v $(shell cd ..; pwd):/fzf junegunn/ubuntu-sandbox \
+		/bin/bash -ci 'cd ~jg/go/src/github.com/junegunn/fzf/src; make build'
+
+.PHONY: build install linux64 clean docker run
diff --git a/src/README.md b/src/README.md
new file mode 100644
index 00000000..2f3ca3bb
--- /dev/null
+++ b/src/README.md
@@ -0,0 +1,59 @@
+fzf in Go
+=========
+
+This directory contains the source code for the new fzf implementation in Go.
+This new version has the following benefits over the previous Ruby version.
+
+- Immensely faster
+    - No GIL. Performance is linearly proportional to the number of cores.
+    - It's so fast that I even decided to remove the sort limit (`--sort=N`)
+- Does not require Ruby and distributed as an executable binary
+    - Ruby dependency is especially painful on Ruby 2.1 or above which
+      ships without curses gem
+
+Build
+-----
+
+```sh
+# Build fzf executable
+make
+
+# Install the executable to ../bin directory
+make install
+
+# Build executable for Linux x86_64 using Docker
+make linux64
+```
+
+
+Prebuilt binaries
+-----------------
+
+- Darwin x86_64
+- Linux x86_64
+
+Third-party libraries used
+--------------------------
+
+- [ncurses](https://www.gnu.org/software/ncurses/)
+- [mattn/go-runewidth](https://github.com/mattn/go-runewidth)
+    - Licensed under [MIT](http://mattn.mit-license.org/2013)
+- [mattn/go-shellwords](https://github.com/mattn/go-shellwords)
+    - Licensed under [MIT](http://mattn.mit-license.org/2014)
+
+Contribution
+------------
+
+For the moment, I will not add or accept any new features until we can be sure
+that the implementation is stable and we have a sufficient number of test
+cases. However, fixes for obvious bugs and new test cases are welcome.
+
+I also care much about the performance of the implementation (that's the
+reason I rewrote the whole thing in Go, right?), so please make sure that your
+change does not result in performance regression. Please be minded that we
+still don't have a quantitative measure of the performance.
+
+License
+-------
+
+- [MIT](LICENSE)
diff --git a/src/algo.go b/src/algo.go
new file mode 100644
index 00000000..16790ba9
--- /dev/null
+++ b/src/algo.go
@@ -0,0 +1,152 @@
+package fzf
+
+import "strings"
+
+/*
+ * String matching algorithms here do not use strings.ToLower to avoid
+ * performance penalty. And they assume pattern runes are given in lowercase
+ * letters when caseSensitive is false.
+ *
+ * In short: They try to do as little work as possible.
+ */
+
+func FuzzyMatch(caseSensitive bool, input *string, pattern []rune) (int, int) {
+	runes := []rune(*input)
+
+	// 0. (FIXME) How to find the shortest match?
+	//    a_____b__c__abc
+	//    ^^^^^^^^^^  ^^^
+	// 1. forward scan (abc)
+	//   *-----*-----*>
+	//   a_____b___abc__
+	// 2. reverse scan (cba)
+	//   a_____b___abc__
+	//            <***
+	pidx := 0
+	sidx := -1
+	eidx := -1
+
+	for index, char := range runes {
+		// This is considerably faster than blindly applying strings.ToLower to the
+		// whole string
+		if !caseSensitive && char >= 65 && char <= 90 {
+			char += 32
+		}
+		if char == pattern[pidx] {
+			if sidx < 0 {
+				sidx = index
+			}
+			if pidx += 1; pidx == len(pattern) {
+				eidx = index + 1
+				break
+			}
+		}
+	}
+
+	if sidx >= 0 && eidx >= 0 {
+		pidx -= 1
+		for index := eidx - 1; index >= sidx; index-- {
+			char := runes[index]
+			if !caseSensitive && char >= 65 && char <= 90 {
+				char += 32
+			}
+			if char == pattern[pidx] {
+				if pidx -= 1; pidx < 0 {
+					sidx = index
+					break
+				}
+			}
+		}
+		return sidx, eidx
+	}
+	return -1, -1
+}
+
+func ExactMatchStrings(caseSensitive bool, input *string, pattern []rune) (int, int) {
+	var str string
+	if caseSensitive {
+		str = *input
+	} else {
+		str = strings.ToLower(*input)
+	}
+
+	if idx := strings.Index(str, string(pattern)); idx >= 0 {
+		prefixRuneLen := len([]rune((*input)[:idx]))
+		return prefixRuneLen, prefixRuneLen + len(pattern)
+	}
+	return -1, -1
+}
+
+/*
+ * This is a basic string searching algorithm that handles case sensitivity.
+ * Although naive, it still performs better than the combination of
+ * strings.ToLower + strings.Index for typical fzf use cases where input
+ * strings and patterns are not very long.
+ *
+ * We might try to implement better algorithms in the future:
+ * http://en.wikipedia.org/wiki/String_searching_algorithm
+ */
+func ExactMatchNaive(caseSensitive bool, input *string, pattern []rune) (int, int) {
+	runes := []rune(*input)
+	numRunes := len(runes)
+	plen := len(pattern)
+	if len(runes) < plen {
+		return -1, -1
+	}
+
+	pidx := 0
+	for index := 0; index < numRunes; index++ {
+		char := runes[index]
+		if !caseSensitive && char >= 65 && char <= 90 {
+			char += 32
+		}
+		if pattern[pidx] == char {
+			pidx += 1
+			if pidx == plen {
+				return index - plen + 1, index + 1
+			}
+		} else {
+			index -= pidx
+			pidx = 0
+		}
+	}
+	return -1, -1
+}
+
+func PrefixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) {
+	runes := []rune(*input)
+	if len(runes) < len(pattern) {
+		return -1, -1
+	}
+
+	for index, r := range pattern {
+		char := runes[index]
+		if !caseSensitive && char >= 65 && char <= 90 {
+			char += 32
+		}
+		if char != r {
+			return -1, -1
+		}
+	}
+	return 0, len(pattern)
+}
+
+func SuffixMatch(caseSensitive bool, input *string, pattern []rune) (int, int) {
+	runes := []rune(strings.TrimRight(*input, " "))
+	trimmedLen := len(runes)
+	diff := trimmedLen - len(pattern)
+	if diff < 0 {
+		return -1, -1
+	}
+
+	for index, r := range pattern {
+		char := runes[index+diff]
+		if !caseSensitive && char >= 65 && char <= 90 {
+			char += 32
+		}
+		if char != r {
+			return -1, -1
+		}
+	}
+	return trimmedLen - len(pattern), trimmedLen
+}
diff --git a/src/algo_test.go b/src/algo_test.go
new file mode 100644
index 00000000..5da01a6d
--- /dev/null
+++ b/src/algo_test.go
@@ -0,0 +1,44 @@
+package fzf
+
+import (
+	"strings"
+	"testing"
+)
+
+func assertMatch(t *testing.T, fun func(bool, *string, []rune) (int, int), caseSensitive bool, input string, pattern string, sidx int, eidx int) {
+	if !caseSensitive {
+		pattern = strings.ToLower(pattern)
+	}
+	s, e := fun(caseSensitive, &input, []rune(pattern))
+	if s != sidx {
+		t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", s, sidx, input, pattern)
+	}
+	if e != eidx {
+		t.Errorf("Invalid end index: %d (expected: %d, %s / %s)", e, eidx, input, pattern)
+	}
+}
+
+func TestFuzzyMatch(t *testing.T) {
+	assertMatch(t, FuzzyMatch, false, "fooBarbaz", "oBZ", 2, 9)
+	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBZ", -1, -1)
+	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBz", 2, 9)
+	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "fooBarbazz", -1, -1)
+}
+
+func TestExactMatchNaive(t *testing.T) {
+	assertMatch(t, ExactMatchNaive, false, "fooBarbaz", "oBA", 2, 5)
+	assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "oBA", -1, -1)
+	assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "fooBarbazz", -1, -1)
+}
+
+func TestPrefixMatch(t *testing.T) {
+	assertMatch(t, PrefixMatch, false, "fooBarbaz", "Foo", 0, 3)
+	assertMatch(t, PrefixMatch, true, "fooBarbaz", "Foo", -1, -1)
+	assertMatch(t, PrefixMatch, false, "fooBarbaz", "baz", -1, -1)
+}
+
+func TestSuffixMatch(t *testing.T) {
+	assertMatch(t, SuffixMatch, false, "fooBarbaz", "Foo", -1, -1)
+	assertMatch(t, SuffixMatch, false, "fooBarbaz", "baz", 6, 9)
+	assertMatch(t, SuffixMatch, true, "fooBarbaz", "Baz", -1, -1)
+}
diff --git a/src/atomicbool.go b/src/atomicbool.go
new file mode 100644
index 00000000..f2f4894f
--- /dev/null
+++ b/src/atomicbool.go
@@ -0,0 +1,27 @@
+package fzf
+
+import "sync"
+
+type AtomicBool struct {
+	mutex sync.Mutex
+	state bool
+}
+
+func NewAtomicBool(initialState bool) *AtomicBool {
+	return &AtomicBool{
+		mutex: sync.Mutex{},
+		state: initialState}
+}
+
+func (a *AtomicBool) Get() bool {
+	a.mutex.Lock()
+	defer a.mutex.Unlock()
+	return a.state
+}
+
+func (a *AtomicBool) Set(newState bool) bool {
+	a.mutex.Lock()
+	defer a.mutex.Unlock()
+	a.state = newState
+	return a.state
+}
diff --git a/src/atomicbool_test.go b/src/atomicbool_test.go
new file mode 100644
index 00000000..0af45701
--- /dev/null
+++ b/src/atomicbool_test.go
@@ -0,0 +1,17 @@
+package fzf
+
+import "testing"
+
+func TestAtomicBool(t *testing.T) {
+	if !NewAtomicBool(true).Get() || NewAtomicBool(false).Get() {
+		t.Error("Invalid initial value")
+	}
+
+	ab := NewAtomicBool(true)
+	if ab.Set(false) {
+		t.Error("Invalid return value")
+	}
+	if ab.Get() {
+		t.Error("Invalid state")
+	}
+}
diff --git a/src/cache.go b/src/cache.go
new file mode 100644
index 00000000..340f3258
--- /dev/null
+++ b/src/cache.go
@@ -0,0 +1,47 @@
+package fzf
+
+import "sync"
+
+type QueryCache map[string][]*Item
+type ChunkCache struct {
+	mutex sync.Mutex
+	cache map[*Chunk]*QueryCache
+}
+
+func NewChunkCache() ChunkCache {
+	return ChunkCache{sync.Mutex{}, make(map[*Chunk]*QueryCache)}
+}
+
+func (cc *ChunkCache) Add(chunk *Chunk, key string, list []*Item) {
+	if len(key) == 0 || !chunk.IsFull() {
+		return
+	}
+
+	cc.mutex.Lock()
+	defer cc.mutex.Unlock()
+
+	qc, ok := cc.cache[chunk]
+	if !ok {
+		cc.cache[chunk] = &QueryCache{}
+		qc = cc.cache[chunk]
+	}
+	(*qc)[key] = list
+}
+
+func (cc *ChunkCache) Find(chunk *Chunk, key string) ([]*Item, bool) {
+	if len(key) == 0 || !chunk.IsFull() {
+		return nil, false
+	}
+
+	cc.mutex.Lock()
+	defer cc.mutex.Unlock()
+
+	qc, ok := cc.cache[chunk]
+	if ok {
+		list, ok := (*qc)[key]
+		if ok {
+			return list, true
+		}
+	}
+	return nil, false
+}
diff --git a/src/chunklist.go b/src/chunklist.go
new file mode 100644
index 00000000..b1f9638d
--- /dev/null
+++ b/src/chunklist.go
@@ -0,0 +1,73 @@
+package fzf
+
+import "sync"
+
+const CHUNK_SIZE int = 100
+
+type Chunk []*Item // >>> []Item
+
+type Transformer func(*string, int) *Item
+
+type ChunkList struct {
+	chunks []*Chunk
+	count  int
+	mutex  sync.Mutex
+	trans  Transformer
+}
+
+func NewChunkList(trans Transformer) *ChunkList {
+	return &ChunkList{
+		chunks: []*Chunk{},
+		count:  0,
+		mutex:  sync.Mutex{},
+		trans:  trans}
+}
+
+func (c *Chunk) push(trans Transformer, data *string, index int) {
+	*c = append(*c, trans(data, index))
+}
+
+func (c *Chunk) IsFull() bool {
+	return len(*c) == CHUNK_SIZE
+}
+
+func (cl *ChunkList) lastChunk() *Chunk {
+	return cl.chunks[len(cl.chunks)-1]
+}
+
+func CountItems(cs []*Chunk) int {
+	if len(cs) == 0 {
+		return 0
+	}
+	return CHUNK_SIZE*(len(cs)-1) + len(*(cs[len(cs)-1]))
+}
+
+func (cl *ChunkList) Count() int {
+	return cl.count
+}
+
+func (cl *ChunkList) Chunks() []*Chunk {
+	return cl.chunks
+}
+
+func (cl *ChunkList) Push(data string) {
+	cl.mutex.Lock()
+	defer cl.mutex.Unlock()
+
+	if len(cl.chunks) == 0 || cl.lastChunk().IsFull() {
+		newChunk := Chunk(make([]*Item, 0, CHUNK_SIZE))
+		cl.chunks = append(cl.chunks, &newChunk)
+	}
+
+	cl.lastChunk().push(cl.trans, &data, cl.count)
+	cl.count += 1
+}
+
+func (cl *ChunkList) Snapshot() []*Chunk {
+	cl.mutex.Lock()
+	defer cl.mutex.Unlock()
+
+	ret := make([]*Chunk, len(cl.chunks))
+	copy(ret, cl.chunks)
+	return ret
+}
diff --git a/src/chunklist_test.go b/src/chunklist_test.go
new file mode 100644
index 00000000..a7daa47e
--- /dev/null
+++ b/src/chunklist_test.go
@@ -0,0 +1,66 @@
+package fzf
+
+import (
+	"fmt"
+	"testing"
+)
+
+func TestChunkList(t *testing.T) {
+	cl := NewChunkList(func(s *string, i int) *Item {
+		return &Item{text: s, index: i * 2}
+	})
+
+	// Snapshot
+	snapshot := cl.Snapshot()
+	if len(snapshot) > 0 {
+		t.Error("Snapshot should be empty now")
+	}
+
+	// Add some data
+	cl.Push("hello")
+	cl.Push("world")
+
+	// Previously created snapshot should remain the same
+	if len(snapshot) > 0 {
+		t.Error("Snapshot should not have changed")
+	}
+
+	// But the new snapshot should contain the added items
+	snapshot = cl.Snapshot()
+	if len(snapshot) != 1 {
+		t.Error("Snapshot should not be empty now")
+	}
+
+	// Check the content of the ChunkList
+	chunk1 := snapshot[0]
+	if len(*chunk1) != 2 {
+		t.Error("Snapshot should contain only two items")
+	}
+	if *(*chunk1)[0].text != "hello" || (*chunk1)[0].index != 0 ||
+		*(*chunk1)[1].text != "world" || (*chunk1)[1].index != 2 {
+		t.Error("Invalid data")
+	}
+	if chunk1.IsFull() {
+		t.Error("Chunk should not have been marked full yet")
+	}
+
+	// Add more data
+	for i := 0; i < CHUNK_SIZE*2; i++ {
+		cl.Push(fmt.Sprintf("item %d", i))
+	}
+
+	// Previous snapshot should remain the same
+	if len(snapshot) != 1 {
+		t.Error("Snapshot should stay the same")
+	}
+
+	// New snapshot
+	snapshot = cl.Snapshot()
+	if len(snapshot) != 3 || !snapshot[0].IsFull() ||
+		!snapshot[1].IsFull() || snapshot[2].IsFull() {
+		t.Error("Expected two full chunks and one more chunk")
+	}
+	if len(*snapshot[2]) != 2 {
+		t.Error("Unexpected number of items")
+	}
+}
diff --git a/src/constants.go b/src/constants.go
new file mode 100644
index 00000000..b0b64dbb
--- /dev/null
+++ b/src/constants.go
@@ -0,0 +1,12 @@
+package fzf
+
+const VERSION = "0.9.0"
+
+const (
+	EVT_READ_NEW EventType = iota
+	EVT_READ_FIN
+	EVT_SEARCH_NEW
+	EVT_SEARCH_PROGRESS
+	EVT_SEARCH_FIN
+	EVT_CLOSE
+)
diff --git a/src/core.go b/src/core.go
new file mode 100644
index 00000000..2601397a
--- /dev/null
+++ b/src/core.go
@@ -0,0 +1,153 @@
+package fzf
+
+import (
+	"fmt"
+	"os"
+	"runtime"
+	"time"
+)
+
+const COORDINATOR_DELAY time.Duration = 100 * time.Millisecond
+
+func initProcs() {
+	runtime.GOMAXPROCS(runtime.NumCPU())
+}
+
+/*
+Reader   -> EVT_READ_FIN
+Reader   -> EVT_READ_NEW        -> Matcher  (restart)
+Terminal -> EVT_SEARCH_NEW      -> Matcher  (restart)
+Matcher  -> EVT_SEARCH_PROGRESS -> Terminal (update info)
+Matcher  -> EVT_SEARCH_FIN      -> Terminal (update list)
+*/
+
+func Run(options *Options) {
+	initProcs()
+
+	opts := ParseOptions()
+
+	if opts.Version {
+		fmt.Println(VERSION)
+		os.Exit(0)
+	}
+
+	// Event channel
+	eventBox := NewEventBox()
+
+	// Chunk list
+	var chunkList *ChunkList
+	if len(opts.WithNth) == 0 {
+		chunkList = NewChunkList(func(data *string, index int) *Item {
+			return &Item{text: data, index: index}
+		})
+	} else {
+		chunkList = NewChunkList(func(data *string, index int) *Item {
+			item := Item{text: data, index: index}
+			tokens := Tokenize(item.text, opts.Delimiter)
+			item.origText = item.text
+			item.text = Transform(tokens, opts.WithNth).whole
+			return &item
+		})
+	}
+
+	// Reader
+	reader := Reader{func(str string) { chunkList.Push(str) }, eventBox}
+	go reader.ReadSource()
+
+	// Matcher
+	patternBuilder := func(runes []rune) *Pattern {
+		return BuildPattern(
+			opts.Mode, opts.Case, opts.Nth, opts.Delimiter, runes)
+	}
+	matcher := NewMatcher(patternBuilder, opts.Sort > 0, eventBox)
+
+	// Defered-interactive / Non-interactive
+	//   --select-1 | --exit-0 | --filter
+	if filtering := opts.Filter != nil; filtering || opts.Select1 || opts.Exit0 {
+		limit := 0
+		var patternString string
+		if filtering {
+			patternString = *opts.Filter
+		} else {
+			if opts.Select1 || opts.Exit0 {
+				limit = 1
+			}
+			patternString = opts.Query
+		}
+		pattern := patternBuilder([]rune(patternString))
+
+		looping := true
+		for looping {
+			eventBox.Wait(func(events *Events) {
+				for evt, _ := range *events {
+					switch evt {
+					case EVT_READ_FIN:
+						looping = false
+						return
+					}
+				}
+			})
+			time.Sleep(COORDINATOR_DELAY)
+		}
+
+		matches, cancelled := matcher.scan(MatchRequest{
+			chunks:  chunkList.Snapshot(),
+			pattern: pattern}, limit)
+
+		if !cancelled && (filtering || opts.Exit0) {
+			if opts.PrintQuery {
+				fmt.Println(patternString)
+			}
+			for _, item := range matches {
+				item.Print()
+			}
+			os.Exit(0)
+		}
+	}
+
+	// Go interactive
+	go matcher.Loop()
+
+	// Terminal I/O
+	terminal := NewTerminal(opts, eventBox)
+	go terminal.Loop()
+
+	// Event coordination
+	reading := true
+	ticks := 0
+	for {
+		delay := true
+		ticks += 1
+		eventBox.Wait(func(events *Events) {
+			defer events.Clear()
+			for evt, value := range *events {
+				switch evt {
+
+				case EVT_READ_NEW, EVT_READ_FIN:
+					reading = reading && evt == EVT_READ_NEW
+					terminal.UpdateCount(chunkList.Count(), !reading)
+					matcher.Reset(chunkList.Snapshot(), terminal.Input(), false)
+
+				case EVT_SEARCH_NEW:
+					matcher.Reset(chunkList.Snapshot(), terminal.Input(), true)
+					delay = false
+
+				case EVT_SEARCH_PROGRESS:
+					switch val := value.(type) {
+					case float32:
+						terminal.UpdateProgress(val)
+					}
+
+				case EVT_SEARCH_FIN:
+					switch val := value.(type) {
+					case []*Item:
+						terminal.UpdateList(val)
+					}
+				}
+			}
+		})
+		if ticks > 3 && delay && reading {
+			time.Sleep(COORDINATOR_DELAY)
+		}
+	}
+}
diff --git a/src/curses/curses.go b/src/curses/curses.go
new file mode 100644
index 00000000..945a3ce4
--- /dev/null
+++