nitc :: model_index
ModelIndex allows you to index mentities then retrieve them by their name
or full_name
.
It offers a set of find_*
methods that can be used to match queries
against entities name.
Because each use is different, ModelIndex only provide base raw search services. All of them return IndexMatches that can be ordered and filtered by the client.
Before searching something from the ModelIndex, you have to index it.
Use the ModelIndex::index
method to do that:
var index = new ModelIndex
for mentity in model.collect_mentities do
index.index(mentity)
end
You can then run queries on the ModelIndex:
for res in index.find("Array").limit(10) do
print res
end
Here some examples of how you can use the ModelIndex.
Use ModelIndex to implement a smart prediction system based on the typed prefix:
var index = new ModelIndex
for mentity in model.collect_mentities do
# We don't really care about definitions
if mentity isa MClassDef or mentity isa MPropDef then continue
index.index(mentity)
end
var typed_prefix = "Arr"
for res in index.find_by_name_prefix(typed_prefix).
uniq. # keep only the best ranked mentity
limit(5). # limit to ten results
sort(new VisibilityComparator, new NameComparator) do # order by visibility then name
print res
end
Will output something like:
Array (1)
ArraySet (2)
ArrayMap (3)
ArrayCmp (4)
ArrayMapKeys (5)
Find methods from a class full_name:
var class_full_name = "core::Array"
for res in index.find_by_full_name_prefix("{class_full_name}::").
uniq. # keep only the best ranked mentity
sort(new VisibilityComparator). # put private in the bottom of the list
limit(5). # limit to ten results
sort(new FullNameComparator) do # order by lexicographic order
print res
end
Will output something like:
* (2)
+ (1)
filled_with (5)
from (3)
with_items (4)
Detect unknown names and suggest corrections:
var name = "Zrray"
if index.find_by_name_prefix(name).is_empty then
printn "`{name}` not found, did you mean: "
printn index.find_by_name_similarity(name).sort(new ScoreComparator).limit(2).join(" or ")
print "?"
end
Will output something like:
`Zrray` not found, did you mean: Array (1) or array (1)?
nitc :: FullNameLengthComparator
Compare two matches by their full name lengthnitc :: model_index $ MClassDef
A definition (an introduction or a refinement) of a class in a modulenitc :: model_index $ MEntity
A named and possibly documented entity in the model.nitc :: model_index $ MModule
A Nit module is usually associated with a Nit source file.nitc :: model_index $ MPropDef
A definition of a property (local property)nitc :: model_index $ MProperty
A service (global property) that generalize method, attribute, etc.nitc $ FullNameLengthComparator
Compare two matches by their full name lengthnitc :: model_index $ MClassDef
A definition (an introduction or a refinement) of a class in a modulenitc :: model_index $ MEntity
A named and possibly documented entity in the model.nitc :: model_index $ MModule
A Nit module is usually associated with a Nit source file.nitc :: model_index $ MPropDef
A definition of a property (local property)nitc :: model_index $ MProperty
A service (global property) that generalize method, attribute, etc.Serializable::inspect
to show more useful information
nitc :: modelbuilder
more_collections :: more_collections
Highly specific, but useful, collections-related classes.serialization :: serialization_core
Abstract services to serialize Nit objects to different formatsnitc :: toolcontext
Common command-line tool infrastructure than handle options and error messagescore :: union_find
union–find algorithm using an efficient disjoint-set data structurenitc :: api_metrics
nitc :: commands_ini
# Search things from the Model
#
# ModelIndex allows you to index mentities then retrieve them by their `name`
# or `full_name`.
# It offers a set of `find_*` methods that can be used to match queries
# against entities name.
#
# Because each use is different, ModelIndex only provide base raw search services.
# All of them return IndexMatches that can be ordered and filtered by the client.
#
# ## Indexing mentities
#
# Before searching something from the ModelIndex, you have to index it.
# Use the `ModelIndex::index` method to do that:
#
# ~~~nitish
# var index = new ModelIndex
# for mentity in model.collect_mentities do
# index.index(mentity)
# end
# ~~~
#
# ## Search mentities
#
# You can then run queries on the ModelIndex:
#
# ~~~nitish
# for res in index.find("Array").limit(10) do
# print res
# end
# ~~~
#
# ## Examples
#
# Here some examples of how you can use the ModelIndex.
#
# ### Smart type prediction
#
# Use ModelIndex to implement a smart prediction system based on the typed prefix:
#
# ~~~nitish
# var index = new ModelIndex
# for mentity in model.collect_mentities do
# # We don't really care about definitions
# if mentity isa MClassDef or mentity isa MPropDef then continue
# index.index(mentity)
# end
#
# var typed_prefix = "Arr"
# for res in index.find_by_name_prefix(typed_prefix).
# uniq. # keep only the best ranked mentity
# limit(5). # limit to ten results
# sort(new VisibilityComparator, new NameComparator) do # order by visibility then name
# print res
# end
# ~~~
#
# Will output something like:
#
# ~~~raw
# Array (1)
# ArraySet (2)
# ArrayMap (3)
# ArrayCmp (4)
# ArrayMapKeys (5)
# ~~~
#
# ### Method autocompletion
#
# Find methods from a class full_name:
#
# ~~~nitish
# var class_full_name = "core::Array"
# for res in index.find_by_full_name_prefix("{class_full_name}::").
# uniq. # keep only the best ranked mentity
# sort(new VisibilityComparator). # put private in the bottom of the list
# limit(5). # limit to ten results
# sort(new FullNameComparator) do # order by lexicographic order
# print res
# end
# ~~~
#
# Will output something like:
#
# ~~~raw
# * (2)
# + (1)
# filled_with (5)
# from (3)
# with_items (4)
# ~~~
#
# ### Name typo detection and suggestion
#
# Detect unknown names and suggest corrections:
#
# ~~~nitish
# var name = "Zrray"
#
# if index.find_by_name_prefix(name).is_empty then
# printn "`{name}` not found, did you mean: "
# printn index.find_by_name_similarity(name).sort(new ScoreComparator).limit(2).join(" or ")
# print "?"
# end
# ~~~
#
# Will output something like:
#
# ~~~raw
# `Zrray` not found, did you mean: Array (1) or array (1)?
# ~~~
module model_index
import model::model_collect
import trees::trie
import trees::bktree
redef class Model
# Keep a direct link to mentities by full name to speed up `mentity_from_uri`
var mentities_by_full_name: HashMap[String, MEntity] is lazy do
var mentities_by_full_name = new HashMap[String, MEntity]
for mentity in collect_mentities do
mentities_by_full_name[mentity.full_name] = mentity
end
return mentities_by_full_name
end
# ModelIndex used to perform searches
var index: ModelIndex is lazy, writable do
var index = new ModelIndex
for mentity in collect_mentities do
if mentity isa MClassDef or mentity isa MPropDef then continue
index.index mentity
end
return index
end
redef fun mentities_by_name(name, filter) do
var res = new Array[MEntity]
if not index.names.has_key(name) then return res
for mentity in index.names[name] do
if filter == null or filter.accept_mentity(mentity) then res.add mentity
end
return res
end
redef fun mentity_by_full_name(full_name, filter) do
if mentities_by_full_name.has_key(full_name) then
var mentity = mentities_by_full_name[full_name]
if filter == null or filter.accept_mentity(mentity) then return mentity
end
return null
end
private var score_sorter = new ScoreComparator
private var vis_sorter = new VisibilityComparator
private var kind_sorter = new MEntityComparator
private var name_sorter = new NameComparator
private var lname_sorter = new NameLengthComparator
private var fname_sorter = new FullNameComparator
private var lfname_sorter = new FullNameLengthComparator
# Search mentities based on a `query` string
#
# Lookup the index for anything matching `query` and return `limit` results.
#
# The algorithm used is the following:
# 1- lookup by name prefix
# 2- lookup by full_name prefix
# 3- loopup by levenshtein distance
#
# At each step if the `limit` is reached, the algorithm stops and returns the results.
fun find(query: String, limit: nullable Int, filter: nullable ModelFilter): Array[MEntity] do
# Find, lookup by name prefix
var matches = index.find_by_name_prefix(query, filter).uniq.
sort(lname_sorter, name_sorter, kind_sorter)
if limit != null and matches.length >= limit then
return matches.limit(limit).rerank.sort(vis_sorter, score_sorter).mentities
end
matches = matches.rerank.sort(vis_sorter, score_sorter)
# If limit not reached, lookup by full_name prefix
var malus = matches.length
var full_matches = new IndexMatches
for match in index.find_by_full_name_prefix(query, filter).
sort(kind_sorter, lfname_sorter, fname_sorter) do
match.score += malus
full_matches.add match
end
matches = matches.uniq
if limit != null and matches.length + full_matches.length >= limit then
matches.add_all full_matches
matches = matches.uniq.limit(limit).rerank.sort(vis_sorter, score_sorter)
return matches.mentities
end
# If limit not reached, lookup by similarity
malus = matches.length
var sim_matches = new IndexMatches
for match in index.find_by_similarity(query, filter).sort(score_sorter, kind_sorter, lname_sorter, name_sorter) do
match.score += malus
sim_matches.add match
end
matches.add_all sim_matches
matches = matches.uniq
if limit != null then matches = matches.limit(limit)
return matches.rerank.sort(vis_sorter, score_sorter).mentities
end
end
# ModelIndex indexes mentities by their name and full name
#
# It provides methods to find mentities based on a prefix or string similarity.
#
# ~~~nitish
# # Build index
# var index = new ModelIndex
# for mentity in model.collect_mentities do
# if mentity isa MClassDef or mentity isa MPropDef then continue
# index.index(mentity)
# end
#
# for e in index.find("Foo").uniq.sort(new ScoreComparator).limit(10) do
# print " * {e.score}: {e.mentity.name} ({e.mentity.full_name})"
# end
# ~~~
class ModelIndex
# List of all indexed mentities.
#
# Faster than traversing the tries.
var mentities = new Array[MEntity]
# Map of all mentities indexed by their `name`
var names = new HashMap[String, Array[MEntity]]
# Prefix tree for mentities `name`
#
# Because multiple mentities can share the same `name`, we use a Trie of
# arrays of mentities.
#
# As for now, we do not index class and property definitions.
# TODO add an option.
var name_prefixes = new Trie[Array[MEntity]]
# Distance tree for mentities `name`
var name_distances = new BKTree
# Map of all mentities indexed by their `full_name`
var full_names = new HashMap[String, MEntity]
# Prefix tree for mentities `full_name`
#
# Even if two mentities cannot share the same `full_name`, we use a Trie of
# arrays of mentities to be consistent with `name_prefixes`.
var full_name_prefixes = new Trie[Array[MEntity]]
# Distance tree for mentities `full_name`
var full_name_distances = new BKTree
# Index `mentity` by it's `MEntity::name`
#
# See `name_prefixes`.
private fun index_by_name(mentity: MEntity) do
var name = mentity.name
# Index name
if not names.has_key(name) then
names[name] = new Array[MEntity]
end
names[name].add mentity
# Index prefix
if not name_prefixes.has_key(name) then
name_prefixes[name] = new Array[MEntity]
end
name_prefixes[name].add mentity
# Index distance
name_distances.add(name)
end
# Index `mentity` by its `MEntity::full_name`
private fun index_by_full_name(mentity: MEntity) do
var name = mentity.full_name
# Index full name
full_names[name] = mentity
# Index prefix
if not full_name_prefixes.has_key(name) then
full_name_prefixes[name] = new Array[MEntity]
end
full_name_prefixes[name].add mentity
# Index distance
full_name_distances.add(name)
end
# Index `mentity` so it can be retrieved by a find query
#
# MEntities are indexed by both name and full_name.
fun index(mentity: MEntity) do
mentities.add mentity
index_by_name mentity
index_by_full_name mentity
end
# Translate Trie results to `SearchResult`
#
# This method is used internally to translate each mentity returned by a prefix
# match in a Trie into a SearchResult that can be ranked by score.
#
# Results from the Trie are returned in a breadth first manner so we get the
# matches ordered by prefix.
# We preserve that order by giving an incremental score to the `array` items.
private fun score_results_incremental(array: Array[Array[MEntity]], filter: nullable ModelFilter): IndexMatches do
var results = new IndexMatches
var score = 1
for mentities in array do
for mentity in mentities do
if filter != null and not filter.accept_mentity(mentity) then continue
results.add new IndexMatch(mentity, score)
end
score += 1
end
return results
end
# Find all mentities where `MEntity::name` matches the `prefix`
fun find_by_name_prefix(prefix: String, filter: nullable ModelFilter): IndexMatches do
return score_results_incremental(name_prefixes.find_by_prefix(prefix), filter)
end
# Find all mentities where `MEntity::full_name` matches the `prefix`
fun find_by_full_name_prefix(prefix: String, filter: nullable ModelFilter): IndexMatches do
return score_results_incremental(full_name_prefixes.find_by_prefix(prefix), filter)
end
# Rank all mentities by the distance between `MEntity::name` and `name`
#
# Use the Levenshtein algorithm on all the indexed mentities `name`.
# Warning: may not scale to large indexes.
fun find_by_name_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
var results = new IndexMatches
for match in name_distances.search(name) do
var dist = match.distance
var mname = match.key
if not names.has_key(mname) then continue
for mentity in names[mname] do
if mentity isa MClassDef or mentity isa MPropDef then continue
if filter != null and not filter.accept_mentity(mentity) then continue
results.add new IndexMatch(mentity, dist)
end
end
return results
end
# Rank all mentities by the distance between `MEntity::full_name` and `full_name`
#
# Use the Levenshtein algorithm on all the indexed mentities `full_name`.
# Warning: may not scale to large indexes.
fun find_by_full_name_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
var results = new IndexMatches
for match in full_name_distances.search(name) do
var dist = match.distance
var mname = match.key
if not full_names.has_key(mname) then continue
var mentity = full_names[mname]
if mentity isa MClassDef or mentity isa MPropDef then continue
if filter != null and not filter.accept_mentity(mentity) then continue
results.add new IndexMatch(mentity, dist)
end
return results
end
# Rank all mentities by the distance between `name` and both the mentity name and full name
fun find_by_similarity(name: String, filter: nullable ModelFilter): IndexMatches do
var results = new IndexMatches
results.add_all find_by_full_name_similarity(name, filter)
results.add_all find_by_name_similarity(name, filter)
return results
end
# Find mentities by name trying first by prefix then by similarity
fun find_by_name(name: String, filter: nullable ModelFilter): IndexMatches do
var results = find_by_name_prefix(name, filter)
results.add_all find_by_name_similarity(name, filter)
return results
end
# Find mentities by full name trying firt by prefix then by similarity
fun find_by_full_name(name: String, filter: nullable ModelFilter): IndexMatches do
var results = find_by_full_name_prefix(name)
results.add_all find_by_full_name_similarity(name, filter)
return results
end
# Find all mentities that matches `name`
#
# 1. try by name prefix
# 2. add full name prefix matches
# 3. try similarity by name
# 4. try similarity by full_name
fun find(name: String, filter: nullable ModelFilter): IndexMatches do
var results = find_by_name_prefix(name, filter)
results.add_all find_by_full_name_prefix(name, filter)
results.add_all find_by_similarity(name, filter)
return results
end
end
# An array of IndexMatch instances returned by the ModelIndex
#
# Index matches can be sorted, filtered and truncated.
#
# Thanks to the fluent interface, the index matches can be manipulated in chain
# from a model index query:
#
# ~~~nitish
# var res = index.find("Foo").
# uniq.
# sort(new ScoreComparator, new MEntityComparator).
# limit(10).
# sort(new VisibilityComparator)
# ~~~
class IndexMatches
super Array[IndexMatch]
# Create a new ModelMatches from an array of matches
#
# Elements are copied.
init from_matches(matches: Array[IndexMatch]) do self.add_all matches
# Sort the matches with `comparator` (or a list of comparators)
#
# Return a new IndexMatches instance with the sorted results.
#
# When more than one comparator is given, the comparators are applied in a
# pipeline where the `n`th comparator is applied only if the `n-1`th comparator
# returned 0.
fun sort(comparator: ScoreComparator...): IndexMatches do
var res = to_a
if comparator.length == 1 then
comparator.first.sort res
else
var comparators = new MatchComparators(comparator)
comparators.sort res
end
return new IndexMatches.from_matches(res)
end
# Limit the matches with `limit`
#
# Return a new IndexMatches instance with only the `limit` first matches.
fun limit(limit: Int): IndexMatches do
var res = new Array[IndexMatch]
for match in self do
if res.length >= limit then break
res.add match
end
return new IndexMatches.from_matches(res)
end
# Remove doublons from the matches
#
# Preverse the lowest score of all the matches for a MEntity.
fun uniq: IndexMatches do
var scores = new HashMap[MEntity, IndexMatch]
var res = new Array[IndexMatch]
for match in self do
var mentity = match.mentity
if scores.has_key(mentity) then
var older = scores[mentity]
if match.score < older.score then older.score = match.score
else
scores[mentity] = match
res.add match
end
end
return new IndexMatches.from_matches(res)
end
# Reset score of each matches to follow `self` order
#
# Usefull when you need to apply one sorter over another.
fun rerank: IndexMatches do
var res = new IndexMatches
for match in self do
res.add match
match.score = res.length
end
return res
end
# Aggregate the mentities for all the matches
#
# Preserve the match order.
fun mentities: Array[MEntity] do
var res = new Array[MEntity]
for match in self do res.add match.mentity
return res
end
end
# An MEntity matched from a ModelIndex
#
# Each match has a `score`. The score should be seen as the distance of
# the match from the query. In other words, the lowest is the score, the more
# relevant is the match.
class IndexMatch
super Comparable
redef type OTHER: IndexMatch
# MEntity matches
var mentity: MEntity
# Score allocated by the search method
#
# A lowest score means a more relevant match.
#
# Scores values are arbitrary, the meaning of `10` vs `2000` really depends
# on the search method producing the match and the comparators used to sort
# the matches.
# The only universal rule is: low score = relevance.
var score: Int is writable
# By default matches are compared only on their score
redef fun <=>(o) do return score <=> o.score
redef fun to_s do return "{mentity} ({score})"
end
# Compare two matches by their score
#
# Since the score can be seen as a distance, we want the lowest score first.
class ScoreComparator
super Comparator
redef type COMPARED: IndexMatch
redef fun compare(o1, o2) do return o1.score <=> o2.score
end
# A pipeline of comparators executed in inclusion order
#
# This class is used internally to agregate the behaviors of multiple comparators.
# Use `IndexMatches::sort(comparator...)` instead.
private class MatchComparators
super ScoreComparator
# Comparator to use in the array order
var comparators: Array[ScoreComparator]
# Compare with each comparator
#
# Return the compare value of the first one to return anything else than 0.
redef fun compare(o1, o2) do
for comparator in comparators do
var c = comparator.compare(o1, o2)
if c != 0 then return c
end
return 0
end
end
# Compare two matches by their MEntity kind
#
# Usefull to order the mentities by kind in this order:
# packages, groups, modules and classes, properties.
class MEntityComparator
super ScoreComparator
# See `MEntity::compare_mentity`
redef fun compare(o1, o2) do
return o1.mentity.mentity_kind_rank <=> o2.mentity.mentity_kind_rank
end
end
# Compare two matches by their MEntity visibility
#
# We reverse the original order so private is at the end of the list.
class VisibilityComparator
super ScoreComparator
redef fun compare(o1, o2) do return o2.mentity.visibility <=> o1.mentity.visibility
end
# Compare two matches by their name in lexicographic order
#
# Generally, for a same score, we want to put A before Z.
class NameComparator
super ScoreComparator
redef fun compare(o1, o2) do return o1.mentity.name <=> o2.mentity.name
end
# Compare two matches by their name length
class NameLengthComparator
super ScoreComparator
redef fun compare(o1, o2) do return o1.mentity.name.length <=> o2.mentity.name.length
end
# Compare two matches by their full_name in lexicographic order
#
# Generally, for a same score, we want to put A before Z.
class FullNameComparator
super ScoreComparator
redef fun compare(o1, o2) do return o1.mentity.full_name <=> o2.mentity.full_name
end
# Compare two matches by their full name length
class FullNameLengthComparator
super ScoreComparator
redef fun compare(o1, o2) do return o1.mentity.full_name.length <=> o2.mentity.full_name.length
end
redef class MEntity
# Compare MEntity class kind
#
# Unknown kind have a virtually high score.
private fun mentity_kind_rank: Int do return 10
end
redef class MPackage
redef fun mentity_kind_rank do return 1
end
redef class MGroup
redef fun mentity_kind_rank do return 2
end
redef class MModule
redef fun mentity_kind_rank do return 3
end
redef class MClass
redef fun mentity_kind_rank do return 4
end
redef class MClassDef
redef fun mentity_kind_rank do return 5
end
redef class MProperty
redef fun mentity_kind_rank do return 6
end
redef class MPropDef
redef fun mentity_kind_rank do return 7
end
src/model/model_index.nit:15,1--672,3