1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Search things from the Model
17 # ModelIndex allows you to index mentities then retrieve them by their `name`
19 # It offers a set of `find_*` methods that can be used to match queries
20 # against entities name.
22 # Because each use is different, ModelIndex only provide base raw search services.
23 # All of them return IndexMatches that can be ordered and filtered by the client.
25 # ## Indexing mentities
27 # Before searching something from the ModelIndex, you have to index it.
28 # Use the `ModelIndex::index` method to do that:
31 # var index = new ModelIndex
33 # for mentity in model.private_view.mentities do
34 # index.index(mentity)
40 # You can then run queries on the ModelIndex:
43 # for res in index.find("Array").limit(10) do
50 # Here some examples of how you can use the ModelIndex.
52 # ### Smart type prediction
54 # Use ModelIndex to implement a smart prediction system based on the typed prefix:
57 # var index = new ModelIndex
59 # for mentity in model.private_view.mentities do
60 # # We don't really care about definitions
61 # if mentity isa MClassDef or mentity isa MPropDef then continue
62 # index.index(mentity)
65 # var typed_prefix = "Arr"
66 # for res in index.find_by_name_prefix(typed_prefix).
67 # uniq. # keep only the best ranked mentity
68 # limit(5). # limit to ten results
69 # sort(new VisibilityComparator, new NameComparator) do # order by visibility then name
74 # Will output something like:
84 # ### Method autocompletion
86 # Find methods from a class full_name:
89 # var class_full_name = "core::Array"
90 # for res in index.find_by_full_name_prefix("{class_full_name}::").
91 # uniq. # keep only the best ranked mentity
92 # sort(new VisibilityComparator). # put private in the bottom of the list
93 # limit(5). # limit to ten results
94 # sort(new FullNameComparator) do # order by lexicographic order
99 # Will output something like:
109 # ### Name typo detection and suggestion
111 # Detect unknown names and suggest corrections:
116 # if index.find_by_name_prefix(name).is_empty then
117 # printn "`{name}` not found, did you mean: "
118 # printn index.find_by_name_similarity(name).sort(new ScoreComparator).limit(2).join(" or ")
123 # Will output something like:
126 # `Zrray` not found, did you mean: Array (1) or array (1)?
130 import model
::model_views
133 # ModelIndex indexes mentities by their name and full name
135 # It provides methods to find mentities based on a prefix or string similarity.
139 # var index = new ModelIndex
140 # for mentity in model.private_view.mentities do
141 # if mentity isa MClassDef or mentity isa MPropDef then continue
142 # index.index(mentity)
145 # for e in index.find("Foo").uniq.sort(new ScoreComparator).limit(10) do
146 # print " * {e.score}: {e.mentity.name} ({e.mentity.full_name})"
151 # List of all indexed mentities.
153 # Faster than traversing the tries.
154 var mentities
= new Array[MEntity]
156 # Prefix tree for mentities `name`
158 # Because multiple mentities can share the same `name`, we use a Trie of
159 # arrays of mentities.
161 # As for now, we do not index class and property definitions.
162 # TODO add an option.
163 var name_prefixes
= new Trie[Array[MEntity]]
165 # Prefix tree for mentities `full_name`
167 # Even if two mentities cannot share the same `full_name`, we use a Trie of
168 # arrays of mentities to be consistent with `name_prefixes`.
169 var full_name_prefixes
= new Trie[Array[MEntity]]
171 # Index `mentity` by it's `MEntity::name`
173 # See `name_prefixes`.
174 private fun index_by_name
(mentity
: MEntity) do
175 var name
= mentity
.name
176 if not name_prefixes
.has_key
(name
) then
177 name_prefixes
[name
] = new Array[MEntity]
179 name_prefixes
[name
].add mentity
182 # Index `mentity` by its `MEntity::full_name`
183 private fun index_by_full_name
(mentity
: MEntity) do
184 var name
= mentity
.full_name
185 if not full_name_prefixes
.has_key
(name
) then
186 full_name_prefixes
[name
] = new Array[MEntity]
188 full_name_prefixes
[name
].add mentity
191 # Index `mentity` so it can be retrieved by a find query
193 # MEntities are indexed by both name and full_name.
194 fun index
(mentity
: MEntity) do
195 mentities
.add mentity
196 index_by_name mentity
197 index_by_full_name mentity
200 # Translate Trie results to `SearchResult`
202 # This method is used internally to translate each mentity returned by a prefix
203 # match in a Trie into a SearchResult that can be ranked by score.
205 # Results from the Trie are returned in a breadth first manner so we get the
206 # matches ordered by prefix.
207 # We preserve that order by giving an incremental score to the `array` items.
208 private fun score_results_incremental
(array
: Array[Array[MEntity]]): IndexMatches do
209 var results
= new IndexMatches
211 for mentities
in array
do
212 for mentity
in mentities
do
213 results
.add
new IndexMatch(mentity
, score
)
220 # Find all mentities where `MEntity::name` matches the `prefix`
221 fun find_by_name_prefix
(prefix
: String): IndexMatches do
222 return score_results_incremental
(name_prefixes
.find_by_prefix
(prefix
))
225 # Find all mentities where `MEntity::full_name` matches the `prefix`
226 fun find_by_full_name_prefix
(prefix
: String): IndexMatches do
227 return score_results_incremental
(full_name_prefixes
.find_by_prefix
(prefix
))
230 # Rank all mentities by the distance between `MEntity::name` and `name`
232 # Use the Levenshtein algorithm on all the indexed mentities `name`.
233 # Warning: may not scale to large indexes.
234 fun find_by_name_similarity
(name
: String): IndexMatches do
235 var results
= new IndexMatches
236 for mentity
in mentities
do
237 if mentity
isa MClassDef or mentity
isa MPropDef then continue
238 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.name
))
243 # Rank all mentities by the distance between `MEntity::full_name` and `full_name`
245 # Use the Levenshtein algorithm on all the indexed mentities `full_name`.
246 # Warning: may not scale to large indexes.
247 fun find_by_full_name_similarity
(name
: String): IndexMatches do
248 var results
= new IndexMatches
249 for mentity
in mentities
do
250 if mentity
isa MClassDef or mentity
isa MPropDef then continue
251 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.full_name
))
256 # Rank all mentities by the distance between `name` and both the mentity name and full name
257 fun find_by_similarity
(name
: String): IndexMatches do
258 var results
= new IndexMatches
259 for mentity
in mentities
do
260 if mentity
isa MClassDef or mentity
isa MPropDef then continue
261 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.name
))
262 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.full_name
))
267 # Find mentities by name trying first by prefix then by similarity
268 fun find_by_name
(name
: String): IndexMatches do
269 var results
= find_by_name_prefix
(name
)
270 for mentity
in mentities
do
271 if mentity
isa MClassDef or mentity
isa MPropDef then continue
272 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.name
))
277 # Find mentities by full name trying firt by prefix then by similarity
278 fun find_by_full_name
(name
: String): IndexMatches do
279 var results
= find_by_full_name_prefix
(name
)
280 for mentity
in mentities
do
281 if mentity
isa MClassDef or mentity
isa MPropDef then continue
282 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.full_name
))
287 # Find all mentities that matches `name`
289 # 1. try by name prefix
290 # 2. add full name prefix matches
291 # 3. try similarity by name
292 # 4. try similarity by full_name
293 fun find
(name
: String): IndexMatches do
294 var results
= find_by_name_prefix
(name
)
296 for result
in find_by_full_name_prefix
(name
) do
300 for mentity
in mentities
do
301 if mentity
isa MClassDef or mentity
isa MPropDef then continue
302 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.name
))
303 results
.add
new IndexMatch(mentity
, name
.levenshtein_distance
(mentity
.full_name
))
309 # An array of IndexMatch instances returned by the ModelIndex
311 # Index matches can be sorted, filtered and truncated.
313 # Thanks to the fluent interface, the index matches can be manipulated in chain
314 # from a model index query:
317 # var res = index.find("Foo").
319 # sort(new ScoreComparator, new MEntityComparator).
321 # sort(new VisibilityComparator)
324 super Array[IndexMatch]
326 # Create a new ModelMatches from an array of matches
328 # Elements are copied.
329 init from_matches
(matches
: Array[IndexMatch]) do self.add_all matches
331 # Sort the matches with `comparator` (or a list of comparators)
333 # Return a new IndexMatches instance with the sorted results.
335 # When more than one comparator is given, the comparators are applied in a
336 # pipeline where the `n`th comparator is applied only if the `n-1`th comparator
338 fun sort
(comparator
: ScoreComparator...): IndexMatches do
340 if comparator
.length
== 1 then
341 comparator
.first
.sort res
343 var comparators
= new MatchComparators(comparator
)
346 return new IndexMatches.from_matches
(res
)
349 # Limit the matches with `limit`
351 # Return a new IndexMatches instance with only the `limit` first matches.
352 fun limit
(limit
: Int): IndexMatches do
353 var res
= new Array[IndexMatch]
355 if res
.length
>= limit
then break
358 return new IndexMatches.from_matches
(res
)
361 # Remove doublons from the matches
363 # Preverse the lowest score of all the matches for a MEntity.
364 fun uniq
: IndexMatches do
365 var scores
= new HashMap[MEntity, IndexMatch]
366 var res
= new Array[IndexMatch]
368 var mentity
= match
.mentity
369 if scores
.has_key
(mentity
) then
370 var older
= scores
[mentity
]
371 if match
.score
< older
.score
then older
.score
= match
.score
373 scores
[mentity
] = match
377 return new IndexMatches.from_matches
(res
)
380 # Reset score of each matches to follow `self` order
382 # Usefull when you need to apply one sorter over another.
383 fun rerank
: IndexMatches do
384 var res
= new IndexMatches
387 match
.score
= res
.length
392 # Aggregate the mentities for all the matches
394 # Preserve the match order.
395 fun mentities
: Array[MEntity] do
396 var res
= new Array[MEntity]
397 for match
in self do res
.add match
.mentity
402 # An MEntity matched from a ModelIndex
404 # Each match has a `score`. The score should be seen as the distance of
405 # the match from the query. In other words, the lowest is the score, the more
406 # relevant is the match.
410 redef type OTHER: IndexMatch
415 # Score allocated by the search method
417 # A lowest score means a more relevant match.
419 # Scores values are arbitrary, the meaning of `10` vs `2000` really depends
420 # on the search method producing the match and the comparators used to sort
422 # The only universal rule is: low score = relevance.
423 var score
: Int is writable
425 # By default matches are compared only on their score
426 redef fun <=>(o
) do return score
<=> o
.score
428 redef fun to_s
do return "{mentity} ({score})"
431 # Compare two matches by their score
433 # Since the score can be seen as a distance, we want the lowest score first.
434 class ScoreComparator
437 redef type COMPARED: IndexMatch
439 redef fun compare
(o1
, o2
) do return o1
.score
<=> o2
.score
442 # A pipeline of comparators executed in inclusion order
444 # This class is used internally to agregate the behaviors of multiple comparators.
445 # Use `IndexMatches::sort(comparator...)` instead.
446 private class MatchComparators
447 super ScoreComparator
449 # Comparator to use in the array order
450 var comparators
: Array[ScoreComparator]
452 # Compare with each comparator
454 # Return the compare value of the first one to return anything else than 0.
455 redef fun compare
(o1
, o2
) do
456 for comparator
in comparators
do
457 var c
= comparator
.compare
(o1
, o2
)
458 if c
!= 0 then return c
464 # Compare two matches by their MEntity kind
466 # Usefull to order the mentities by kind in this order:
467 # packages, groups, modules and classes, properties.
468 class MEntityComparator
469 super ScoreComparator
471 # See `MEntity::compare_mentity`
472 redef fun compare
(o1
, o2
) do
473 return o1
.mentity
.mentity_kind_rank
<=> o2
.mentity
.mentity_kind_rank
477 # Compare two matches by their MEntity visibility
479 # We reverse the original order so private is at the end of the list.
480 class VisibilityComparator
481 super ScoreComparator
483 redef fun compare
(o1
, o2
) do return o2
.mentity
.visibility
<=> o1
.mentity
.visibility
486 # Compare two matches by their name in lexicographic order
488 # Generally, for a same score, we want to put A before Z.
490 super ScoreComparator
492 redef fun compare
(o1
, o2
) do return o1
.mentity
.name
<=> o2
.mentity
.name
495 # Compare two matches by their name length
496 class NameLengthComparator
497 super ScoreComparator
499 redef fun compare
(o1
, o2
) do return o1
.mentity
.name
.length
<=> o2
.mentity
.name
.length
502 # Compare two matches by their full_name in lexicographic order
504 # Generally, for a same score, we want to put A before Z.
505 class FullNameComparator
506 super ScoreComparator
508 redef fun compare
(o1
, o2
) do return o1
.mentity
.full_name
<=> o2
.mentity
.full_name
511 # Compare two matches by their full name length
512 class FullNameLengthComparator
513 super ScoreComparator
515 redef fun compare
(o1
, o2
) do return o1
.mentity
.full_name
.length
<=> o2
.mentity
.full_name
.length
520 # Compare MEntity class kind
522 # Unknown kind have a virtually high score.
523 private fun mentity_kind_rank
: Int do return 10
527 redef fun mentity_kind_rank
do return 1
531 redef fun mentity_kind_rank
do return 2
535 redef fun mentity_kind_rank
do return 3
539 redef fun mentity_kind_rank
do return 4
542 redef class MClassDef
543 redef fun mentity_kind_rank
do return 5
546 redef class MProperty
547 redef fun mentity_kind_rank
do return 6
551 redef fun mentity_kind_rank
do return 7