define(function(require,exports,module){const _=require("thirdparty/lodash");function SearchResult(label){this.label=label}function findSpecialCharacters(str){var i,c,specials=[0],lastSegmentSpecialsIndex=0,lastWasLowerCase=!1;for(i=0;i<str.length;i++)"/"===(c=str[i])?(specials.push(i++),specials.push(i),lastSegmentSpecialsIndex=specials.length-1,lastWasLowerCase=!1):"."===c||"-"===c||"_"===c?(specials.push(i),"/"!==str[i+1]&&specials.push(++i),lastWasLowerCase=!1):c.toUpperCase()===c?(lastWasLowerCase&&specials.push(i),lastWasLowerCase=!1):lastWasLowerCase=!0;return{specials:specials,lastSegmentSpecialsIndex:lastSegmentSpecialsIndex}}var SPECIALS_MATCH=0,ANY_MATCH=1,DEBUG_SCORES=!1;function _setDebugScores(ds){DEBUG_SCORES=ds}var SPECIAL_POINTS=40,MATCH_POINTS=10,UPPER_CASE_MATCH=100,CONSECUTIVE_MATCHES_POINTS=8,BEGINNING_OF_NAME_POINTS=13,LAST_SEGMENT_BOOST=1,DEDUCTION_FOR_LENGTH=.2,NOT_STARTING_ON_SPECIAL_PENALTY=25;function SpecialMatch(index,upper){this.index=index,upper&&(this.upper=upper)}function NormalMatch(index,upper){this.index=index,upper&&(this.upper=upper)}function _generateMatchList(query,str,originalQuery,originalStr,specials,startingSpecial){var result=[],specialsCounter=startingSpecial,strCounter=specials[startingSpecial],queryCounter,deadBranches=[];for(queryCounter=0;queryCounter<query.length;queryCounter++)deadBranches[queryCounter]=1/0;queryCounter=0;var state=SPECIALS_MATCH;function findMatchingSpecial(){var i;for(i=specialsCounter;i<specials.length&&!(specials[i]>=deadBranches[queryCounter]);i++)if(specials[i]<strCounter)specialsCounter=i;else if(query[queryCounter]===str[specials[i]]){strCounter=specials[i];var upper=originalQuery[queryCounter]===originalStr[strCounter]&&originalStr[strCounter]!==str[strCounter];return result.push(new SpecialMatch(strCounter,upper)),specialsCounter=i,queryCounter++,strCounter++,!0}return!1}function backtrack(){for(;result.length>0;){var item=result.pop();if(!item)return!1;if(queryCounter--,item instanceof SpecialMatch&&(specialsCounter--,item.index<deadBranches[queryCounter]))return deadBranches[queryCounter]=item.index-1,state=ANY_MATCH,(item=result[result.length-1])?(strCounter=item.index+1,!0):(strCounter=specials[startingSpecial]+1,!0)}return!1}for(;;){for(;queryCounter<query.length&&strCounter<str.length&&strCounter<=deadBranches[queryCounter];)if(state===SPECIALS_MATCH&&(findMatchingSpecial()||(state=ANY_MATCH)),state===ANY_MATCH)if(query[queryCounter]===str[strCounter]){var upper=originalQuery[queryCounter]===originalStr[strCounter]&&originalStr[strCounter]!==str[strCounter];result.push(new NormalMatch(strCounter++,upper)),queryCounter++,state=SPECIALS_MATCH}else strCounter++;if(queryCounter>=query.length||queryCounter<query.length&&!backtrack())break}return queryCounter<query.length||0===result.length?null:result}function _lastSegmentSearch(query,str,originalQuery,originalStr,specials,startingSpecial,lastSegmentStart){var queryCounter,matchList,remainder="",originalRemainder="",extraCharacters=specials[startingSpecial]+query.length-str.length;for(extraCharacters>0&&(remainder=query.substring(0,extraCharacters),originalRemainder=originalQuery.substring(0,extraCharacters),query=query.substring(extraCharacters),originalQuery=originalQuery.substring(extraCharacters)),queryCounter=0;queryCounter<query.length&&(!(matchList=_generateMatchList(query.substring(queryCounter),str,originalQuery.substring(queryCounter),originalStr,specials,startingSpecial))&&0!==startingSpecial);queryCounter++);return queryCounter!==query.length&&matchList?{remainder:remainder+query.substring(0,queryCounter),originalRemainder:originalRemainder+originalQuery.substring(0,queryCounter),matchList:matchList}:null}function _wholeStringSearch(queryLower,compareLower,originalQuery,originalStr,specials,lastSegmentSpecialsIndex){var lastSegmentStart=specials[lastSegmentSpecialsIndex],result,matchList;if(result=_lastSegmentSearch(queryLower,compareLower,originalQuery,originalStr,specials,lastSegmentSpecialsIndex,lastSegmentStart)){if(matchList=result.matchList,result.remainder){var remainderMatchList=_generateMatchList(result.remainder,compareLower.substring(0,lastSegmentStart),result.originalRemainder,originalStr.substring(0,lastSegmentStart),specials.slice(0,lastSegmentSpecialsIndex),0);if(!remainderMatchList)return null;matchList.unshift.apply(matchList,remainderMatchList)}}else matchList=_generateMatchList(queryLower,compareLower,originalQuery,originalStr,specials,0);return matchList}function _computeRangesAndScore(matchList,str,lastSegmentStart){var matchCounter,ranges=[],lastMatchIndex=-1,lastSegmentScore=0,currentRangeStartedOnSpecial=!1,score=0,scoreDebug;DEBUG_SCORES&&(scoreDebug={special:0,match:0,upper:0,lastSegment:0,beginning:0,lengthDeduction:0,consecutive:0,notStartingOnSpecial:0});var currentRange=null;function closeRangeGap(c){currentRange&&(currentRange.includesLastSegment=lastMatchIndex>=lastSegmentStart,currentRange.matched&&currentRange.includesLastSegment&&(DEBUG_SCORES&&(scoreDebug.lastSegment+=lastSegmentScore*LAST_SEGMENT_BOOST),score+=lastSegmentScore*LAST_SEGMENT_BOOST),currentRange.matched&&!currentRangeStartedOnSpecial&&(DEBUG_SCORES&&(scoreDebug.notStartingOnSpecial-=NOT_STARTING_ON_SPECIAL_PENALTY),score-=NOT_STARTING_ON_SPECIAL_PENALTY),ranges.push(currentRange)),lastMatchIndex+1<c&&ranges.push({text:str.substring(lastMatchIndex+1,c),matched:!1,includesLastSegment:c>lastSegmentStart}),currentRange=null,lastSegmentScore=0}var numConsecutive=0;function addMatch(match){var c=match.index,newPoints=0;if(DEBUG_SCORES&&(scoreDebug.match+=MATCH_POINTS),newPoints+=MATCH_POINTS,match.upper&&(DEBUG_SCORES&&(scoreDebug.upper+=UPPER_CASE_MATCH),newPoints+=UPPER_CASE_MATCH),c===lastSegmentStart&&(DEBUG_SCORES&&(scoreDebug.beginning+=BEGINNING_OF_NAME_POINTS),newPoints+=BEGINNING_OF_NAME_POINTS),score>0&&lastMatchIndex+1===c){c-numConsecutive===lastSegmentStart&&(DEBUG_SCORES&&(scoreDebug.beginning+=BEGINNING_OF_NAME_POINTS),newPoints+=BEGINNING_OF_NAME_POINTS);var boost=CONSECUTIVE_MATCHES_POINTS*++numConsecutive;currentRangeStartedOnSpecial&&(boost*=2),DEBUG_SCORES&&(scoreDebug.consecutive+=boost),newPoints+=boost}else numConsecutive=1;match instanceof SpecialMatch&&(DEBUG_SCORES&&(scoreDebug.special+=SPECIAL_POINTS),newPoints+=SPECIAL_POINTS),score+=newPoints,c>=lastSegmentStart&&(lastSegmentScore+=newPoints),(currentRange&&!currentRange.matched||c>lastMatchIndex+1)&&closeRangeGap(c),lastMatchIndex=c,currentRange?currentRange.text+=str[c]:(currentRange={text:str[c],matched:!0},currentRangeStartedOnSpecial=match instanceof SpecialMatch)}for(matchCounter=0;matchCounter<matchList.length;matchCounter++){var match;addMatch(matchList[matchCounter])}closeRangeGap(str.length);var lengthPenalty=-1*Math.round(str.length*DEDUCTION_FOR_LENGTH);DEBUG_SCORES&&(scoreDebug.lengthDeduction=lengthPenalty);var result={ranges:ranges,matchGoodness:score+=lengthPenalty};return DEBUG_SCORES&&(result.scoreDebug=scoreDebug),result}function _prefixMatchResult(str,query){var result=new SearchResult(str);return result.matchGoodness=-Number.MAX_VALUE,str.substr(0,query.length)!==query&&(result.matchGoodness*=.5),DEBUG_SCORES&&(result.scoreDebug={beginning:-result.matchGoodness}),result.stringRanges=[{text:str.substr(0,query.length),matched:!0,includesLastSegment:!0}],str.length>query.length&&result.stringRanges.push({text:str.substring(query.length),matched:!1,includesLastSegment:!0}),result}function _computeMatchingRanges(query="",searchString="",includeNonContiguous){let index=searchString.toLowerCase().indexOf(query.toLowerCase());return includeNonContiguous&&console.error("includeNonContiguous option is not supported in _computeMatchingRanges"),-1===index?null:0===index&&query.length===searchString.length?[{text:searchString,matched:!0}]:0===index?[{text:searchString.slice(0,query.length),matched:!0},{text:searchString.slice(query.length),matched:!1}]:index+query.length===searchString.length?[{text:searchString.slice(0,index),matched:!1},{text:searchString.slice(index),matched:!0}]:[{text:searchString.slice(0,index),matched:!1},{text:searchString.substring(index,index+query.length),matched:!0},{text:searchString.slice(index+query.length),matched:!1}]}function _codeHintsRelevanceSort(result,query,prefixListLower,maxResults,onlyContiguous){const queryLower=query.toLowerCase();if(!prefixListLower)return result;prefixListLower=prefixListLower.map(prefix=>prefix.toLowerCase());const filteredPrefixMapLower={};for(let prefixLower of prefixListLower)prefixLower.startsWith(queryLower)&&(filteredPrefixMapLower[prefixLower]=!0);const resultsWithPrefix={},startingWithResults=[],endingWithResults=[],contiguousResults=[],disjointResults=[];let resultItemLabelLower,fullMatchStartIndex,fullMatchIndexFromEnd;for(const resultItem of result)if(fullMatchIndexFromEnd=-1,-1!==(fullMatchStartIndex=(resultItemLabelLower=resultItem.label.toLowerCase()).indexOf(queryLower))&&(fullMatchIndexFromEnd=resultItemLabelLower.length-(fullMatchStartIndex+queryLower+1)),filteredPrefixMapLower[resultItemLabelLower]?(resultsWithPrefix[resultItemLabelLower]=resultItem,resultItem.matchGoodness=+Number.MAX_VALUE):0===fullMatchStartIndex?(startingWithResults.push(resultItem),resultItem.matchGoodness=+Number.MAX_VALUE):0===fullMatchIndexFromEnd||1===fullMatchIndexFromEnd?(endingWithResults.push(resultItem),resultItem.matchGoodness=+Number.MAX_VALUE):resultItemLabelLower.includes(queryLower)?(contiguousResults.push(resultItem),resultItem.matchGoodness=+Number.MAX_VALUE):disjointResults.push(resultItem),maxResults&&resultsWithPrefix.length===maxResults)break;const orderedResults=[];for(let prefixItemLower of prefixListLower)resultsWithPrefix[prefixItemLower]&&orderedResults.push(resultsWithPrefix[prefixItemLower]);let totalResultCount=orderedResults.length;function _mergeResults(resultArray){for(let resultItem of resultArray){if(maxResults&&totalResultCount>=maxResults)break;orderedResults.push(resultItem),totalResultCount++}}return _mergeResults(startingWithResults),_mergeResults(endingWithResults),_mergeResults(contiguousResults),onlyContiguous?orderedResults:(_mergeResults(disjointResults),orderedResults)}function stringMatch(str,query,options,special){var result;if(options=options||{},!query)return(result=new SearchResult(str)).matchGoodness=0,DEBUG_SCORES&&(result.scoreDebug={}),result.stringRanges=[{text:str,matched:!1,includesLastSegment:!0}],result;var queryLower=query.toLowerCase(),compareLower=str.toLowerCase(),lastSegmentStart,matchList;if(options.preferPrefixMatches&&(options.segmentedSearch=!1),options.preferPrefixMatches&&compareLower.substr(0,queryLower.length)===queryLower)return _prefixMatchResult(str,query);if(special||(special=findSpecialCharacters(str)),options.segmentedSearch?(lastSegmentStart=special.specials[special.lastSegmentSpecialsIndex],matchList=_wholeStringSearch(queryLower,compareLower,query,str,special.specials,special.lastSegmentSpecialsIndex)):(lastSegmentStart=0,matchList=_generateMatchList(queryLower,compareLower,query,str,special.specials,0)),matchList){var compareData=_computeRangesAndScore(matchList,str,lastSegmentStart);(result=new SearchResult(str)).stringRanges=compareData.ranges,result.matchGoodness=-1*compareData.matchGoodness,DEBUG_SCORES&&(result.scoreDebug=compareData.scoreDebug)}return result}function multiFieldSort(searchResults,fieldSpec){var comparisons;Array.isArray(fieldSpec)?comparisons=fieldSpec:(comparisons=[],_.forEach(fieldSpec,function(priority,key){comparisons[priority]=key})),searchResults.sort(function(a,b){var priority;for(priority=0;priority<comparisons.length;priority++){var comparison=comparisons[priority];if("function"==typeof comparison){var result=comparison(a,b);if(result)return result}else{var valueA=a[comparison],valueB=b[comparison];if("string"==typeof valueA&&(valueA=valueA.toLowerCase(),valueB=valueB.toLowerCase()),valueA<valueB)return-1;if(valueA>valueB)return 1}}return 0})}function basicMatchSort(searchResults){multiFieldSort(searchResults,{matchGoodness:0,label:1})}const codeHintsMatcherOptions={preferPrefixMatches:!0};function codeHintsSort(query,choices,options){let choice,results=[];options=options||{};for(let i=0;i<choices.length;i++){const result=stringMatch(choice=choices[i],query,codeHintsMatcherOptions);result&&(result.sourceIndex=i,query||delete result.stringRanges,results.push(result))}if(basicMatchSort(results),results=_codeHintsRelevanceSort(results,query,options.boostPrefixList||[],options.limit,options.onlyContiguous),!query)return results;for(let result of results){const ranges=_computeMatchingRanges(query,result.label);ranges&&(result.stringRanges=ranges)}return results}function StringMatcher(options){this.options=options,this.reset()}StringMatcher.prototype._specialsCache=null,StringMatcher.prototype._noMatchCache=null,StringMatcher.prototype.reset=function(){this._lastQuery=null,this._specialsCache={},this._noMatchCache={}},StringMatcher.prototype.match=function(str,query){if(null!==this._lastQuery&&this._lastQuery!==query.substring(0,this._lastQuery.length)&&(this._noMatchCache={}),this._lastQuery=query,!_.has(this._noMatchCache,str)){var special=_.has(this._specialsCache,str)?this._specialsCache[str]:void 0;void 0===special&&(special=findSpecialCharacters(str),this._specialsCache[str]=special);var result=stringMatch(str,query,this.options,special);return result||(this._noMatchCache[str]=!0),result}},exports._findSpecialCharacters=findSpecialCharacters,exports._wholeStringSearch=_wholeStringSearch,exports._lastSegmentSearch=_lastSegmentSearch,exports._setDebugScores=_setDebugScores,exports._generateMatchList=_generateMatchList,exports._SpecialMatch=SpecialMatch,exports._NormalMatch=NormalMatch,exports._computeRangesAndScore=_computeRangesAndScore,exports.SearchResult=SearchResult,exports.stringMatch=stringMatch,exports.basicMatchSort=basicMatchSort,exports.multiFieldSort=multiFieldSort,exports.codeHintsSort=codeHintsSort,exports.StringMatcher=StringMatcher});