function lProbeSitesAll = analyzeProfilingTraceInfo...
    (startSymbol, endSymbol, traceInfo, srcFiles)
%ANALYZEPROFILINGTRACEINFO

%   Copyright 2014 The MathWorks, Inc.

    lProbeInsertionInfo = traceInfo.getModelToCodeRecords;
    N = length(lProbeInsertionInfo);
    
    lProbeSitesAll = struct('FileNameIdx', {}, ...
        'TraceId', {}, ...
        'StartFcnCharNo', {}, ...
        'StartLineNo', {}, ...
        'StartColNo', {}, ...                         
        'EndFcnCharNo', {},  ...
        'EndLineNo', {}, ... 
        'EndColNo', {} ...                         
        );
    
    if N==0
        return;
    end
    
    % Initialize tokens data
    tokensStr = {};
    tokens = lProbeInsertionInfo(1).tokens([]); 
    
    for i=1:N 
        tokens_tmp = lProbeInsertionInfo(i).tokens; 
        tokensStr_tmp = lProbeInsertionInfo(i).SID;
        [tokensStr{(end+1):(end+length(tokens_tmp))}] = deal(tokensStr_tmp);
        [tokens((end+1):(end+length(tokens_tmp)))] = deal(lProbeInsertionInfo(i).tokens(:)); 
    end

    expr = ['((' startSymbol ')|(' endSymbol ')):([0-9]+)'];
    probeNames = regexprep(tokensStr, expr, '$1', 'once');
    probeIds = regexprep(tokensStr, expr, '$2', 'once');
    probeIds = str2double(probeIds);
    isStartProbe = strcmp(probeNames, startSymbol);
     
    % Process each file separately
    for i=1:length(srcFiles)
        srcFile = srcFiles{i};
        lProbeSites = i_probeSitesForFile...
            (srcFile, tokens, i, isStartProbe, probeIds);
        N = length(lProbeSites);
        lProbeSitesAll(end+1:end+N) = i_probeSitesForFile...
            (srcFile, tokens, i, isStartProbe, probeIds);
    end
end

function lProbeSites = i_probeSitesForFile...
        (srcFile, tokens, fileIdx, isStartProbeAll, probeIdsAll)
   
    lProbeSites = struct('FileNameIdx', {}, ...
        'TraceId', {}, ...
        'StartFcnCharNo', {}, ...
        'StartLineNo', {}, ...
        'StartColNo', {}, ...                         
        'EndFcnCharNo', {},  ...
        'EndLineNo', {}, ... 
        'EndColNo', {} ...                         
        );
    
    % Filter out data for other files
    idx = strcmp({tokens.file}, srcFile);
    if ~any(idx)
        return;
    end
    tokens = tokens(idx);
    isStartProbeAll = isStartProbeAll(idx);
    probeIdsAll = probeIdsAll(idx);
    
    % Sort the tokens by position in the file
    N = length(tokens);
    lineNos = {};
    beginColNos = {};
    [lineNos{1:N}] = deal(tokens(:).line);
    [beginColNos{1:N}] = deal(tokens(:).beginCol);
    [endColNos{1:N}] = deal(tokens(:).endCol);
    charNos = coder.profile.lineAndColToChar(...
        [lineNos(:) lineNos(:)], ...
        [beginColNos(:) endColNos(:)], ...
        srcFile);
    beginCharNos = cell2mat(charNos(:, 1));
    [~, sortIdx] = sort(beginCharNos);
    beginCharNos = beginCharNos(sortIdx);
    endCharNos = cell2mat(charNos(sortIdx, 2));
    tokens = tokens(sortIdx);
    isStartProbeAll = isStartProbeAll(sortIdx);
    probeIdsAll = probeIdsAll(sortIdx);
    lineNos = lineNos(sortIdx);
    beginColNos = beginColNos(sortIdx);
    endColNos = endColNos(sortIdx);
       
    tokenIds = {tokens(:).id};
    tokenIds = cell2mat(tokenIds);
    [keepIdx, startIdx, endIdx] = i_analyze_calltree...
        (probeIdsAll, tokenIds, isStartProbeAll);
    N = length(startIdx);
    charNosMatched = cell(N,2);
    lineNosMatched = cell(N,2);
    colNosMatched = cell(N,2);
    srcFilesIdx = cell(N, 1);
    probeIdsSub = cell(N, 1);
    for ii2 = 1:N
        idxStart = keepIdx(startIdx(ii2));
        idxEnd = keepIdx(endIdx(ii2));
        charNosMatched(ii2, :) = {beginCharNos(idxStart), endCharNos(idxEnd)};
        colNosMatched(ii2, :) = {beginColNos{idxStart}, endColNos{idxEnd}};
        lineNosMatched(ii2,:) = {lineNos{idxStart}, lineNos{idxEnd}};
        probeIdsSub{ii2} = probeIdsAll(idxStart);
        srcFilesIdx{ii2} = fileIdx; % repeated for each entry
    end
    lProbeSites(1:N) = struct('FileNameIdx', srcFilesIdx, ...
                              'TraceId', probeIdsSub, ...
                              'StartFcnCharNo', charNosMatched(:,1), ...
                              'StartLineNo', lineNosMatched(:, 1), ...
                              'StartColNo', colNosMatched(:, 1), ...
                              'EndFcnCharNo', charNosMatched(:,2), ...
                              'EndLineNo', lineNosMatched(:, 2), ...
                              'EndColNo', colNosMatched(:, 2) ...
                              );
end


function removeIdx = i_emptyProbes(tokenIds_in, matchIdx_in, ...
    isStartProbe_in)

% Identify probes that don't enclose any tokens
removeIdx = ((tokenIds_in(matchIdx_in)-tokenIds_in)==1 & ~isStartProbe_in)...
    | ...
    ((tokenIds_in(matchIdx_in)-tokenIds_in)==-1 & isStartProbe_in);
end


function [startIdx, endIdx] = i_analyze_probe_tree(tokenIds, probeIds, isStartProbe)

tokenIdsStart = tokenIds(isStartProbe);
probeIdsStart = probeIds(isStartProbe);
startIdx = find(isStartProbe);

% Now evaluate the probe tree
rootNode = 0;
probeTree = zeros(size(tokenIdsStart));
nextNode = rootNode+1;
endIdx = zeros(size(tokenIdsStart));
depth = 1;
stack = rootNode;
for i=1:length(tokenIds)
    if isStartProbe(i)
        % push a node onto the stack
        parentId = stack(depth);
        newNodeId = nextNode;
        nextNode = nextNode+1;
        probeTree(newNodeId) = parentId;
        depth = depth+1;
        stack(depth) = newNodeId;
    else
        % pop a node
        nodeId = stack(depth);
        probeIdStart = probeIdsStart(nodeId);
        assert(probeIdStart==probeIds(i), ...
            'Start and end probes must occur in matched pairs');
        endIdx(nodeId) = i;
        depth = depth-1;
    end
end

end


function sortIdx = i_sort_by_code_location(tokenIds_in, isStartProbe_in, ...
    matchIdx_in)

% Apply rules in reverse order of priority

% Rule 1: affinity of start and end tokens is proportional to their distance apart
sortKey =  - tokenIds_in(matchIdx_in);

% Rule 2: end tokens must precede start tokens
sortKey = sortKey + int32(intmax('int32') / 2) * int32(isStartProbe_in);

% Rule 3: sort in order of token id
sortKey = int64(sortKey) + int64(tokenIds_in)*int64(2^32);

[~, sortIdx] = sort(sortKey);

end

    
function  [keepIdx, startIdx, endIdx] = i_analyze_calltree...
    (probeIds_in, tokenIds_in, isStartProbe_in)

% Identify the matching start/end pairs
matchIdx_in = feval(class(probeIds_in), zeros(size(probeIds_in)));
[~, ib, ic] = unique(probeIds_in);
for i=1:length(ib)
    pairIdx = find(i==ic);
    for ii1 = 1:length(pairIdx)/2
        matchIdx_in(pairIdx(2*ii1-1)) = pairIdx(2*ii1);
        matchIdx_in(pairIdx(2*ii1)) = pairIdx(2*ii1-1);
    end
end

% First identify probes that are enclose no tokens
removeIdx_in = i_emptyProbes(tokenIds_in, matchIdx_in, isStartProbe_in);

% Now sort the probes corresponding to the order that the should be
% inserted in the instrumented code
sortIdx = i_sort_by_code_location(tokenIds_in, isStartProbe_in, matchIdx_in);

% Apply the sort and remove
keepIdx = 1:length(sortIdx);
tokenIds = tokenIds_in(sortIdx);
probeIds = probeIds_in(sortIdx);
isStartProbe = isStartProbe_in(sortIdx);
removeIdx = removeIdx_in(sortIdx);
keepIdx = keepIdx(sortIdx);

tokenIds = tokenIds(~removeIdx);
probeIds = probeIds(~removeIdx);
isStartProbe = isStartProbe(~removeIdx);
keepIdx = keepIdx(~removeIdx);

probeIds = i_fixNestedProbes(probeIds, tokenIds, isStartProbe);

[startIdx, endIdx] = i_analyze_probe_tree(tokenIds, probeIds, isStartProbe);

end

function probeIds = i_fixNestedProbes (probeIds, tokenIds, isStartProbe)
% fix the termination order for probes on the same line, e.g.: 
% profile_start(1); profile_start(2); fcn(x); profile_stop(2); profile_stop(1);
% in the inputs we have: probeIds=[1 2 1 2], isStartProbe=[1 1 0 0];
% in other words, the probe 1 ends when the nested probe 2 is still active
% this function detects this condition and update probeIds=[1 2 2 1]

alreadyChecked = false(size(probeIds));
for i=1:length(probeIds)-1
    if isStartProbe(i) && ~alreadyChecked(i)
        % find end line of the current probe
        positions = find(probeIds == probeIds(i));
        endPos = positions(2);
        endLine = tokenIds(endPos);
        startLine = tokenIds(i);
        % find probes with the same start and stop line
        startsOnTheSameLine = (tokenIds == startLine) & isStartProbe;
        endsOnTheSameLine   = (tokenIds == endLine) & ~isStartProbe;
        startIDsOnTheSameLine = probeIds(startsOnTheSameLine);
        endIDsOnTheSameLine   = probeIds(endsOnTheSameLine);
        IDsOnTheSameStatement = intersect(startIDsOnTheSameLine, endIDsOnTheSameLine);
        % take all ends and invert their order
        endsToDealWith = false(size(probeIds));
        startsToDealWith = false(size(probeIds));
        for j=i:length(probeIds)
            if ~alreadyChecked(j) && ismember(probeIds(j), IDsOnTheSameStatement)
                if isStartProbe(j)
                    startsToDealWith(j) = true;
                else
                    endsToDealWith(j) = true;
                end
            end
        end
        oldEndOrder = probeIds(endsToDealWith);
        newEndOrder = fliplr(oldEndOrder);
        idx = 1;
        for j=i:length(endsToDealWith)
            if endsToDealWith(j)
                probeIds(j) = newEndOrder(idx);
                idx = idx + 1;
            end
        end
        % marked all their start as done
        alreadyChecked(startsToDealWith) = true;
    end
end
end

