core/org.eclipse.statet.rj.server/src/org/eclipse/statet/rj/server/rh/AbstractTracepointManager.java

/*=============================================================================#
 # Copyright (c) 2017, 2020 Stephan Wahlbrink and others.
 # 
 # This program and the accompanying materials are made available under the
 # terms of the Eclipse Public License 2.0 which is available at
 # https://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
 # which is available at https://www.apache.org/licenses/LICENSE-2.0.
 # 
 # SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
 # 
 # Contributors:
 #     Stephan Wahlbrink <sw@wahlbrink.eu> - initial API and implementation
 #=============================================================================*/

package org.eclipse.statet.rj.server.rh;

import static org.eclipse.statet.jcommons.lang.ObjectUtils.nonNullAssert;

import static org.eclipse.statet.rj.server.dbg.Srcfiles.equalsTimestamp;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.LOGGER;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.containsPositionsById;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.equalsPositions;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.filterPositionsById;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.filterPositionsByIdRequired;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.findIndexByReference;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.findIndexBySrcref;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.getSrcrefForIndex;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.indexOfTracepointById;
import static org.eclipse.statet.rj.server.dbg.Tracepoints.rebasePositionsByIndex;
import static org.eclipse.statet.rj.server.rh.ObjectManager.WEAK_REF;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.LogRecord;

import org.eclipse.statet.jcommons.collections.CopyOnWriteIdentityListSet;
import org.eclipse.statet.jcommons.collections.IdentitySet;
import org.eclipse.statet.jcommons.collections.ImCollections;
import org.eclipse.statet.jcommons.collections.ImList;
import org.eclipse.statet.jcommons.collections.SortedArraySet;
import org.eclipse.statet.jcommons.lang.NonNull;
import org.eclipse.statet.jcommons.lang.NonNullByDefault;
import org.eclipse.statet.jcommons.lang.Nullable;
import org.eclipse.statet.jcommons.lang.ObjectUtils;

import org.eclipse.statet.rj.server.RjsException;
import org.eclipse.statet.rj.server.RjsStatus;
import org.eclipse.statet.rj.server.dbg.DbgListener;
import org.eclipse.statet.rj.server.dbg.ElementTracepointInstallationRequest;
import org.eclipse.statet.rj.server.dbg.ElementTracepoints;
import org.eclipse.statet.rj.server.dbg.FlagTracepointInstallationRequest;
import org.eclipse.statet.rj.server.dbg.SrcfileData;
import org.eclipse.statet.rj.server.dbg.Srcref;
import org.eclipse.statet.rj.server.dbg.Tracepoint;
import org.eclipse.statet.rj.server.dbg.TracepointEvent;
import org.eclipse.statet.rj.server.dbg.TracepointPosition;
import org.eclipse.statet.rj.server.dbg.TracepointState;
import org.eclipse.statet.rj.server.dbg.TracepointStatesUpdate;
import org.eclipse.statet.rj.server.dbg.Tracepoints;
import org.eclipse.statet.rj.server.rh.ObjectManager.EnvListener;


@NonNullByDefault
public abstract class AbstractTracepointManager {
	
	
	protected static final String TOPLEVEL_ELEMENT_ID= "200:"; //$NON-NLS-1$
	
	private static final String ENV_INSTALLED_TAG= "#" + WEAK_REF + ":dbg.tracepoints";
	
	
	private static final int MAX_HISTORY= 12;
	private static final int MAX_FUZZY= 8;
	
	
	protected static final class StateSet extends SortedArraySet<@NonNull StateEntry> {
		
		
		public StateSet(final int initialSize) {
			super(new @NonNull StateEntry[initialSize], 0, null);
		}
		
		
		protected static final int binarySearchId(final StateEntry[] a, int begin, int end, final long id) {
			end--;
			while (begin <= end) {
				final int i= (begin + end) >>> 1;
				final int d= a[i].compareToId(id);
				if (d < 0) {
					begin= i + 1;
				}
				else if (d > 0) {
					end= i - 1;
				}
				else {
					return i;
				}
			}
			return -(begin + 1);
		}
		
		public int indexOfId(final long id) {
			return binarySearchId(array(), 0, size(), id);
		}
		
	}
	
	
	private static final boolean containsCommonElement(final List<? extends ElementTracepoints> list) {
		for (final ElementTracepoints element : list) {
			if (!element.getElementId().equals(TOPLEVEL_ELEMENT_ID)) {
				return true;
			}
		}
		return false;
	}
	
	private static final int indexOfStateEntry(final List<StateEntry> entries,
			final long id) {
		for (int idx= 0; idx < entries.size(); idx++) {
			if (entries.get(idx).getId() == id) {
				return idx;
			}
		}
		return -1;
	}
	
	protected static final @Nullable StateEntry getBreakpointState(final StateSet states,
			final long id) {
		final int idx= states.indexOfId(id);
		if (idx >= 0) {
			final StateEntry entry= states.get(idx);
			final TracepointState state= entry.getState();
			if (state != null
					&& (state.getType() & Tracepoint.TYPE_BREAKPOINT) != 0) {
				return entry;
			}
		}
		return null;
	}
	
	protected static final @Nullable StateEntry getBreakpointState(final StateSet states,
			final @Nullable String elementId, final int @Nullable [] index) {
		if (elementId != null && index != null) {
			for (int i= 0; i < states.size(); i++) {
				final StateEntry entry= states.get(i);
				final TracepointState state= entry.getState();
				if (state != null
						&& (state.getType() & Tracepoint.TYPE_BREAKPOINT) != 0
						&& elementId.equals(state.getElementId())
						&& Arrays.equals(index, state.getIndex()) ) {
					return entry;
				}
			}
		}
		return null;
	}
	
	private static final boolean isAllDeleted(final List<? extends TracepointPosition> positions,
			final StateSet states) {
		return false;
//		synchronized (states) {
//			for (final TracepointPosition position : positions) {
//				final int idx= states.indexOfId(position.getId());
//				if (idx >= 0 && states.get(idx).getState() != null) {
//					return false;
//				}
//			}
//		}
//		return true;
	}
	
	
	protected static final ImList<TracepointPosition> NO_POSITIONS= ImCollections.emptyList();
	protected static final ElementTracepoints NO_POSITION_ELEMENT_TRACEPOINTS= new ElementTracepoints(
			new SrcfileData(null, null, 0), "", null, NO_POSITIONS ); //$NON-NLS-1$
	protected static final ElementTracepoints NO_CHANGE_ELEMENT_TRACEPOINTS= new ElementTracepoints(
			new SrcfileData(null, null, 0), "", null, NO_POSITIONS ); //$NON-NLS-1$
	
	
	/**
	 * Collection of (best matching) element tracepoints for current tracepoint positions.
	 */
	protected final static class ElementTracepointsCollection {
		
		
		private final long updatingStamp;
		
		private final ElementTracepoints current;
		
		private final List<ElementTracepoints> list;
		
		private final long requestedTimestamp;
		
		
		public ElementTracepointsCollection(final long updatingStamp,
				final ElementTracepoints current, final List<ElementTracepoints> list,
				final long requestedTimestamp) {
			this.updatingStamp= updatingStamp;
			this.current= current;
			this.list= list;
			this.requestedTimestamp= requestedTimestamp;
		}
		
		public ElementTracepointsCollection(final long updatingStamp,
				final ElementTracepoints current, final ElementTracepoints single,
				final long requestedTimestamp) {
			this.updatingStamp= updatingStamp;
			this.current= current;
			this.list= ImCollections.newList(single);
			this.requestedTimestamp= requestedTimestamp;
		}
		
		
		public long getUpdatingStamp() {
			return this.updatingStamp;
		}
		
		public ElementTracepoints getCurrent() {
			return this.current;
		}
		
		public List<ElementTracepoints> getList() {
			return this.list;
		}
		
		public boolean isActualPositionsEmpty() {
			return this.current.getPositions().isEmpty();
		}
		
		public List<? extends TracepointPosition> getActualPositions(final List<? extends TracepointPosition> positions) {
			return filterPositionsByIdRequired(positions, this.current.getPositions());
		}
		
		public long getRequestedTimestamp() {
			return this.requestedTimestamp;
		}
		
	}
	
	
	protected static class PathEntry {
		
		
		private final String path;
		
		private long updateStamp;
		private @Nullable SrcfileData srcfile;
		
		private final List<ElementEntry> elementEntries= new ArrayList<>();
		
		private final StateSet states= new StateSet(8);
		
		private final List<ElementTracepointsCollection> updatingInstalled= new ArrayList<>();
		
		
		public PathEntry(final String path) {
			this.path= path;
		}
		
		
		public final String getPath() {
			return this.path;
		}
		
		public final long getUpdateStamp() {
			return this.updateStamp;
		}
		
		private int indexOf(final String id) {
			int low= 0;
			int high= this.elementEntries.size() - 1;
			while (low <= high) {
				final int mid= (low + high) >>> 1;
				final int diff= this.elementEntries.get(mid).id.compareTo(id);
				if (diff < 0) {
					low= mid + 1;
				}
				else if (diff > 0) {
					high= mid - 1;
				}
				else {
					return mid;
				}
			}
			return -(low + 1);
		}
		
		private ElementEntry ensureElement(final String id) {
			final int idx= indexOf(id);
			if (idx >= 0) {
				return this.elementEntries.get(idx);
			}
			else {
				final ElementEntry entry= new ElementEntry(id);
				this.elementEntries.add(-(idx + 1), entry);
				return entry;
			}
		}
		
		/** Adds or updates current positions */
		private void addTracepoints(final ElementTracepoints tracepoints, final long updateStamp) {
			synchronized (this.elementEntries) {
				this.updateStamp= updateStamp;
				this.srcfile= tracepoints.getSrcfile();
				
				final ElementEntry elementEntry= ensureElement(
						(tracepoints.getElementId().startsWith(TOPLEVEL_ELEMENT_ID)) ?
								TOPLEVEL_ELEMENT_ID : tracepoints.getElementId() );
				elementEntry.setTracepoints(tracepoints, updateStamp);
			}
		}
		
		public @Nullable ElementEntry getElementEntry(final String id) {
			synchronized (this.elementEntries) {
				final int idx= indexOf(id);
				return (idx >= 0) ? this.elementEntries.get(idx) : null;
			}
		}
		
		public @Nullable ElementTracepoints findElementTracepoints(
				final @Nullable String id, final long timestamp) {
			if (id == null) {
				return null;
			}
			final ElementEntry elementEntry= getElementEntry(id);
			return (elementEntry != null) ?
					elementEntry.findTracepoints(timestamp, this.states) :
					null;
		}
		
		/**
		 * Returns list with single CurrentPositionCollection for current tracepoint positions.
		 * @param timestamp timestamp of srcfile or <code>0</code>
		 * @param srcref srcref of element to match or <code>null</code>
		 * @return list with CurrentPositionCollection or <code>null</code>
		 */
		public @Nullable ElementTracepointsCollection findCurrentElementTracepoints(
				final @Nullable String id, final long timestamp, final int @Nullable [] srcref) {
			if (id == null && srcref == null) {
				return null;
			}
			
			ElementEntry elementEntry= null;
			boolean isNestedMatch= false;
			if (id != null) { // by id
				elementEntry= getElementEntry(id);
			}
			else if (timestamp != 0) { // by timestamp
				synchronized (this.elementEntries) {
					for (final ElementEntry entry : this.elementEntries) {
						if (entry.getId() == TOPLEVEL_ELEMENT_ID) {
							continue;
						}
						final ElementTracepoints cand= entry.getTracepoints(timestamp);
						if (cand != null && cand.getElementSrcref() != null
								&& Srcref.contains(cand.getElementSrcref(), srcref) ) {
							if (Srcref.equalsStart(cand.getElementSrcref(), srcref)) {
								elementEntry= entry;
								isNestedMatch= false;
								break;
							}
							else {
								elementEntry= entry;
								isNestedMatch= true;
							}
						}
					}
				}
			}
			else {
				synchronized (this.elementEntries) {
					ElementTracepoints best= null;
					boolean requireDim= false;
					for (final ElementEntry entry : this.elementEntries) {
						if (entry.getId() == TOPLEVEL_ELEMENT_ID) {
							continue;
						}
						final ElementTracepoints cand= entry.getCurrentTracepoints();
						if (cand != null && cand.getElementSrcref() != null
								&& Srcref.equalsStart(cand.getElementSrcref(), srcref)
								&& !isAllDeleted(cand.getPositions(), this.states) ) {
							if (Srcref.equalsDim(cand.getElementSrcref(), srcref)) {
								if (!requireDim) {
									requireDim= true;
									best= null;
								}
							}
							else {
								if (requireDim) {
									continue;
								}
							}
							if (best == null || entry.getUpdateStamp() > elementEntry.getUpdateStamp()) {
								elementEntry= entry;
								best= cand;
							}
						}
					}
					if (requireDim && best != null) {
						return new ElementTracepointsCollection(elementEntry.getUpdateStamp(),
								best, best, timestamp );
					}
				}
			}
			return (elementEntry != null) ?
					(isNestedMatch) ?
							elementEntry.findCurrentNestedTracepoints(timestamp, srcref, this.states) :
							elementEntry.findCurrentTracepoints(timestamp, srcref, this.states) :
					null;
		}
		
		
		/** Returns the list with current states. Synchronization required! */
		public StateSet getStates() {
			return this.states;
		}
		
		public @Nullable StateEntry getBreakpointState(final long id) {
			synchronized (this.states) {
				return AbstractTracepointManager.getBreakpointState(this.states, id);
			}
		}
		
		
		public void addInstalled(final ElementTracepointsCollection collection) {
			this.updatingInstalled.add(collection);
		}
		
		private void finishUpdatingInst(final RhEnv env, final boolean clear,
				final StateSet installed, final StateSet changed) {
			synchronized (this.states) {
				for (int i= 0; i < this.states.size(); i++) {
					final StateEntry stateEntry= this.states.get(i);
					int isInstalled= 0;
					boolean isUpdated= false;
					for (int j= 0; j < this.updatingInstalled.size(); j++) {
						final ElementTracepointsCollection collection= this.updatingInstalled.get(j);
						if (indexOfTracepointById(collection.getCurrent().getPositions(), stateEntry.getId()) >= 0) {
							isInstalled++;
							isUpdated|= stateEntry.addUpdatingInstElement(collection);
						}
					}
					
					if (isInstalled > 0) {
						if (!stateEntry.instEnvs.contains(env) && stateEntry.instEnvs.add(env)) {
							changed.add(stateEntry);
							if (LOGGER.isLoggable(Level.FINE)) {
								LOGGER.log(Level.FINE,
										"[TP] Updating element tracepoint {0}: installed in {2} element(s) of {1} now.",
										new Object[] {
												stateEntry,
												env,
												(clear) ? isInstalled : "one or more" } );
							}
						}
						else if (isUpdated) {
							changed.add(stateEntry);
						}
						installed.add(stateEntry);
					}
					else if (clear) {
						if (stateEntry.instEnvs.remove(env)) {
							if (stateEntry.instEnvs.isEmpty()) {
								changed.add(stateEntry);
							}
							if (LOGGER.isLoggable(Level.FINE)) {
								LOGGER.log(Level.FINE,
										"[TP] Updating element tracepoint {0}: installed in NO element of {1} now.",
										new Object[] {
												stateEntry,
												env } );
							}
						}
					}
				}
			}
			
			this.updatingInstalled.clear();
		}
		
	}
	
	protected static class ElementEntry {
		
		
		private final String id;
		
		private final List<ElementTracepoints> history= new ArrayList<>();
		
		private long updateStamp;
		
		
		public ElementEntry(final String id) {
			this.id= id;
		}
		
		
		public final String getId() {
			return this.id;
		}
		
		
		/** Sets current element tracepoints */
		protected void setTracepoints(final ElementTracepoints tracepoints, final long updateStamp) {
			this.updateStamp= updateStamp;
			if (this.history.isEmpty()) {
				this.history.add(tracepoints);
			}
			else if (this.history.get(0).getSrcfile().getTimestamp() == tracepoints.getSrcfile().getTimestamp()) {
				this.history.set(0, tracepoints);
			}
			else {
				if (this.history.size() >= MAX_HISTORY) {
					this.history.remove(this.history.size() - 1);
				}
				this.history.add(0, tracepoints);
			}
		}
		
		public long getUpdateStamp() {
			return this.updateStamp;
		}
		
		/** Returns current element tracepoints */
		public @Nullable ElementTracepoints getCurrentTracepoints() {
			synchronized (this.history) {
				return (!this.history.isEmpty()) ? this.history.get(0) : null;
			}
		}
		
		/** Returns positions for specified timestamp */
		public @Nullable ElementTracepoints getTracepoints(final long timestamp) {
			synchronized (this.history) {
				if (!this.history.isEmpty()) {
					if (timestamp != 0) {
						for (int i= 0; i < this.history.size(); i++) {
							final ElementTracepoints cand= this.history.get(i);
							if (equalsTimestamp(cand.getSrcfile().getTimestamp(), timestamp)) {
								return cand;
							}
						}
					}
				}
				return null;
			}
		}
		
		public @Nullable ElementTracepoints findTracepoints(
				final long timestamp,
				final @Nullable StateSet states) {
			synchronized (this.history) {
				if (!this.history.isEmpty()) {
					final ElementTracepoints current= this.history.get(0);
					int end= this.history.size();
					if (states != null && !current.getPositions().isEmpty()
							&& isAllDeleted(current.getPositions(), states) ) {
						return NO_POSITION_ELEMENT_TRACEPOINTS;
					}
					if (end > 1 && !current.getPositions().isEmpty()) {
						ElementTracepoints best= null;
						List<TracepointPosition> timestampPositions= null;
						if (timestamp != 0) {
							for (int i= 0; i < end; i++) {
								final ElementTracepoints cand= this.history.get(i);
								if (equalsTimestamp(cand.getSrcfile().getTimestamp(), timestamp)) {
									if (containsPositionsById(cand.getPositions(), current.getPositions())) {
										return cand;
									}
									best= cand;
									timestampPositions= filterPositionsById(cand.getPositions(), current.getPositions());
									end= i;
									break;
								}
							}
							if (timestampPositions != null && !timestampPositions.isEmpty() ) {
								for (int i= 0; i < end; i++) {
									final ElementTracepoints cand= this.history.get(i);
									if (equalsPositions(cand.getPositions(), timestampPositions,
											timestampPositions )) {
										return cand;
									}
								}
							}
						}
						if (best != null) {
							return best;
						}
					}
					return current;
				}
				return null;
			}
		}
		
		/** Returns CurrentPositionCollection with current tracepoints positions */
		public @Nullable ElementTracepointsCollection findCurrentTracepoints(
				final long timestamp, final int @Nullable [] srcref,
				final @Nullable StateSet states) {
			synchronized (this.history) {
				if (!this.history.isEmpty()) {
					final ElementTracepoints current= this.history.get(0);
					int end= this.history.size();
					if (states != null && !current.getPositions().isEmpty()
							&& isAllDeleted(current.getPositions(), states) ) {
						return new ElementTracepointsCollection(this.updateStamp,
								NO_POSITION_ELEMENT_TRACEPOINTS, NO_POSITION_ELEMENT_TRACEPOINTS, 0 );
					}
					if (end > 1 && !current.getPositions().isEmpty()) {
						if (timestamp != 0) {
							List<TracepointPosition> timestampActualPositions= null;
							for (int i= 0; i < end; i++) {
								final ElementTracepoints cand= this.history.get(i);
								if (equalsTimestamp(cand.getSrcfile().getTimestamp(), timestamp)) {
									if (containsPositionsById(cand.getPositions(), current.getPositions())) {
										return new ElementTracepointsCollection(this.updateStamp,
												current, cand, timestamp );
									}
									timestampActualPositions= filterPositionsById(cand.getPositions(), current.getPositions());
									end= i;
									break;
								}
							}
							if (timestampActualPositions != null && !timestampActualPositions.isEmpty()) {
								for (int i= 0; i < end; i++) {
									final ElementTracepoints cand= this.history.get(i);
									if (containsPositionsById(cand.getPositions(), current.getPositions())
											&& equalsPositions(cand.getPositions(), timestampActualPositions,
														timestampActualPositions )) {
										return new ElementTracepointsCollection(this.updateStamp,
												current, cand, timestamp );
									}
								}
							}
						}
						if (srcref != null) {
							final List<ElementTracepoints> selected= new ArrayList<>(MAX_FUZZY);
							selected.add(current);
							for (int i= 1; i < end && selected.size() < MAX_FUZZY; i++) {
								final ElementTracepoints cand= this.history.get(i);
								if (cand.getElementSrcref() != null
										&& Srcref.equalsDim(cand.getElementSrcref(), srcref)
										&& containsPositionsById(cand.getPositions(), current.getPositions())
										&& !equalsPositions(cand.getPositions(),
												selected.get(selected.size() - 1).getPositions(),
												current.getPositions() )) {
									selected.add(cand);
								}
							}
							return new ElementTracepointsCollection(this.updateStamp,
									current, selected, timestamp );
						}
					}
					return new ElementTracepointsCollection(this.updateStamp,
							current, current, timestamp );
				}
				return null;
			}
		}
		
		public @Nullable ElementTracepointsCollection findCurrentNestedTracepoints(
				final long timestamp, final int[] srcref,
				final @Nullable StateSet states) {
			synchronized (this.history) {
				if (!this.history.isEmpty()) {
					final ElementTracepoints current= this.history.get(0);
					int end= this.history.size();
					if (current.getPositions().isEmpty()
							|| (states != null && isAllDeleted(current.getPositions(), states)) ) {
						return createNoPositionCollection();
					}
					if (timestamp != 0) {
						int[] timestampSrcref= null;
						List<TracepointPosition> timestampPositions= null;
						for (int i= 0; i < end; i++) {
							final ElementTracepoints cand= this.history.get(i);
							if (equalsTimestamp(cand.getSrcfile().getTimestamp(), timestamp)) {
								if (cand.getElementSrcref() == null) {
									break;
								}
								final int[] index= findIndexBySrcref(cand.getPositions(),
										nonNullAssert(cand.getElementSrcref()), srcref );
								if (index != null) {
									timestampSrcref= nonNullAssert(getSrcrefForIndex(
											cand.getPositions(), index ));
									timestampPositions= rebasePositionsByIndex(
											cand.getPositions(), index );
									if (containsPositionsById(cand.getPositions(), current.getPositions())) {
										return createNestedCollection(current,
												createNested(cand, timestampSrcref, filterPositionsById(
														timestampPositions, current.getPositions() )),
												timestamp, states );
									}
								}
								end= i;
								break;
							}
						}
						if (timestampPositions != null && !timestampPositions.isEmpty()) {
							for (int i= 0; i < end; i++) {
								final ElementTracepoints cand= this.history.get(i);
								if (containsPositionsById(cand.getPositions(), current.getPositions())) {
									final List<TracepointPosition> compareList= filterPositionsById(
											cand.getPositions(), timestampPositions );
									final int[] index= findIndexByReference(compareList, timestampPositions);
									if (index != null) {
										final int[] candSrcref= nonNullAssert(getSrcrefForIndex(
												compareList, index ));
										final List<TracepointPosition> candPositions= rebasePositionsByIndex(
												cand.getPositions(), index );
										if (equalsPositions(candPositions, timestampPositions,
												timestampPositions )) {
											return createNestedCollection(current,
													createNested(cand, candSrcref, filterPositionsById(
															candPositions, current.getPositions() )),
													timestamp, states );
										}
									}
								}
							}
							{	final List<TracepointPosition> positions= filterPositionsById(
										timestampPositions, current.getPositions() );
								if (positions.isEmpty()
										|| (states != null && isAllDeleted(positions, states)) ) {
									return createNoPositionCollection();
								}
							}
						}
						return createNoChangeCollection();
					}
				}
				return null;
			}
		}
		
		private ElementTracepointsCollection createNoPositionCollection() {
			return new ElementTracepointsCollection(this.updateStamp,
					NO_POSITION_ELEMENT_TRACEPOINTS, NO_POSITION_ELEMENT_TRACEPOINTS, 0 );
		}
		
		private ElementTracepointsCollection createNoChangeCollection() {
			return new ElementTracepointsCollection(this.updateStamp,
					NO_CHANGE_ELEMENT_TRACEPOINTS, NO_CHANGE_ELEMENT_TRACEPOINTS, 0 );
		}
		
		private ElementTracepoints createNested(final ElementTracepoints cand,
				final int[] srcref, final List<TracepointPosition> nestedPositions) {
			return new ElementTracepoints(cand.getSrcfile(), this.id, srcref, nestedPositions);
		}
		
		private ElementTracepointsCollection createNestedCollection(final ElementTracepoints current,
				final ElementTracepoints nested, final long requestedTimestamp,
				final @Nullable StateSet states) {
			final List<TracepointPosition> currentPositions= filterPositionsById(
					current.getPositions(), nested.getPositions());
			if (currentPositions.isEmpty()
					|| (states != null && isAllDeleted(currentPositions, states)) ) {
				return createNoPositionCollection();
			}
			return new ElementTracepointsCollection(this.updateStamp,
					new ElementTracepoints(current.getSrcfile(), this.id, null, currentPositions),
					nested, requestedTimestamp );
		}
		
	}
	
	protected class StateEntry implements Comparable<StateEntry> {
		
		private final String path;
		private final long id;
		
		private final List<RhEnv> instEnvs= new ArrayList<>();
		private @Nullable ElementTracepoints instElement;
		private long instUpdatingStamp;
		
		private @Nullable ElementTracepointsCollection updatingInstElement;
		
		private @Nullable TracepointState state;
		
		private @Nullable ParsedExpr parsedExpr;
		
		
		public StateEntry(final String path, final long id) {
			this.path= path;
			this.id= id;
		}
		
		
		public final long getId() {
			return this.id;
		}
		
		public final boolean isInstalled() {
			return !this.instEnvs.isEmpty();
		}
		
		public synchronized void setState(final TracepointState state) {
			this.state= state;
		}
		
		public synchronized final @Nullable TracepointState getState() {
			return this.state;
		}
		
		public synchronized ParsedExpr getParsedExpr(final String source) {
			ParsedExpr pe= this.parsedExpr;
			if (pe != null) {
				if (pe.getSource().equals(source)) {
					return pe;
				}
				AbstractTracepointManager.this.objManager.addToDispose(pe);
				this.parsedExpr= null;
			}
			pe= new ParsedExpr(source);
			if (this.state != null) {
				this.parsedExpr= pe;
			}
			return pe;
		}
		
		public synchronized void removed() {
			this.state= null;
			if (this.parsedExpr != null) {
				AbstractTracepointManager.this.objManager.addToDispose(this.parsedExpr);
				this.parsedExpr= null;
			}
		}
		
		
		private @Nullable TracepointEvent checkInstalled(final @Nullable ElementTracepoints prevElement) {
			final ElementTracepoints element= this.instElement;
			if (element != null && element != prevElement
					&& (prevElement == null
							|| !element.getElementId().equals(prevElement.getElementId()) )) {
				return new TracepointEvent(TracepointEvent.KIND_INSTALLED,
						0, element.getSrcfile().getPath(), this.id,
						element.getElementId(), null, 0 );
			}
			return null;
		}
		
		private @Nullable TracepointEvent checkUninstalled() {
			final ElementTracepoints element= this.instElement;
			if (element != null) {
				this.instElement= null;
				return new TracepointEvent(TracepointEvent.KIND_UNINSTALLED,
							0, element.getSrcfile().getPath(), this.id,
							element.getElementId(), null, 0 );
			}
			return null;
		}
		
		
		private boolean addUpdatingInstElement(final ElementTracepointsCollection collection) {
			if (this.updatingInstElement == null
					|| collection.getUpdatingStamp() > this.updatingInstElement.getUpdatingStamp()) {
				this.updatingInstElement= collection;
				return true;
			}
			return false;
		}
		
		private void finishUpdatingInst(final List<TracepointEvent> events) {
			TracepointEvent event= null;
			
			if (isInstalled()) {
				final ElementTracepoints prevElement= this.instElement;
				if (this.updatingInstElement != null
						&& (getClearUpdatingInst()
								|| this.instElement == null
								|| this.updatingInstElement.getUpdatingStamp() > this.instUpdatingStamp )) {
					this.instElement= this.updatingInstElement.getCurrent();
					this.instUpdatingStamp= this.updatingInstElement.getUpdatingStamp();
					event= checkInstalled(prevElement);
				}
			}
			else {
				event= checkUninstalled();
			}
			if (event != null) {
				events.add(event);
			}
			this.updatingInstElement= null;
		}
		
		private void removeInst(final RhEnv env, final List<TracepointEvent> events) {
			TracepointEvent event= null;
			if (isInstalled() && this.instEnvs.remove(env)
					&& this.instEnvs.isEmpty() ) {
				event= checkUninstalled();
			}
			if (event != null) {
				events.add(event);
			}
		}
		
		
		@Override
		public int compareTo(final StateEntry other) {
			return (this.id < other.id) ? -1 : (this.id != other.id) ? 1 :
					this.path.compareTo(other.path);
		}
		
		private int compareToId(final long otherId) {
			return (this.id < otherId) ? -1 : (this.id != otherId) ? 1 : 0;
		}
		
		@Override
		public final int hashCode() {
			return Long.hashCode(this.id);
		}
		
		@Override
		public final boolean equals(final @Nullable Object obj) {
			return (this == obj
					|| (obj instanceof StateEntry
							&& this.id == ((StateEntry) obj).id
							&& this.path.equals(((StateEntry) obj).path)) );
		}
		
		@Override
		public String toString() {
			final StringBuilder sb= new StringBuilder(16 + 6 + this.path.length());
			Tracepoints.append(this.id, sb);
			sb.append(" in '");
			sb.append(this.path);
			sb.append('\'');
			return sb.toString();
		}
		
	}
	
	
	protected final ObjectManager objManager;
	private final DbgListener listener;
	
	private final Map<String, PathEntry> pathMap= new HashMap<>(32);
	private @Nullable ImList<PathEntry> pathList;
	private final Object stateUpdate= new Object();
	private volatile boolean isAnyEnabled;
	
	private final IdentitySet<String> envTags= new CopyOnWriteIdentityListSet<>();
	
	private boolean isBreakpointsEnabled= true;
	
	private @Nullable RhEnv updatingEnv;
	private boolean updatingEnvComplete;
	private final StateSet updatingStates= new StateSet(32);
	
	
	public AbstractTracepointManager(final ObjectManager objManager, final DbgListener listener) {
		this.objManager= objManager;
		this.listener= listener;
		
		this.objManager.addEnvListener(new EnvListener() {
			@Override
			public void onEnvRemoved(final RhEnv env, final boolean finalized) {
				if (finalized && env.isReg(ENV_INSTALLED_TAG)) {
					updateInstOnRemoved(env);
				}
			}
		});
	}
	
	
	protected boolean isAnyTracepointEnabled() {
		return this.isAnyEnabled;
	}
	
	protected PathEntry ensurePathEntry(final String path) {
		synchronized (this.pathMap) {
			PathEntry entry= this.pathMap.get(path);
			if (entry == null) {
				entry= new PathEntry(path);
				this.pathMap.put(path, entry);
				this.pathList= null;
			}
			return entry;
		}
	}
	
	protected ImList<PathEntry> getPathEntries() {
		synchronized (this.pathMap) {
			ImList<PathEntry> pathList= this.pathList;
			if (pathList == null) {
				pathList= ImCollections.toList(this.pathMap.values());
				this.pathList= pathList;
			}
			return pathList;
		}
	}
	
	protected @Nullable PathEntry getPathEntry(final String path) {
		synchronized (this.pathMap) {
			return this.pathMap.get(path);
		}
	}
	
	protected @Nullable PathEntry findPathEntryByFileName(final String fileName) {
		synchronized (this.pathMap) {
			for (final PathEntry entry : this.pathMap.values()) {
				final SrcfileData srcfile= entry.srcfile;
				if (srcfile != null && fileName.equals(srcfile.getName())) {
					return entry;
				}
			}
			return null;
		}
	}
	
	private void addTracepoints(final ElementTracepoints tracepoints, final long updateStamp) {
		final SrcfileData srcfile= tracepoints.getSrcfile();
		final String srcfilePath= srcfile.getPath();
		if (srcfilePath != null) {
			final PathEntry entry= ensurePathEntry(srcfilePath);
			entry.addTracepoints(tracepoints, updateStamp);
		}
	}
	
	protected void addTracepoints(final List<? extends ElementTracepoints> tracepointsList) {
		final long updateStamp= System.nanoTime();
		for (final ElementTracepoints tracepoints : tracepointsList) {
			addTracepoints(tracepoints, updateStamp);
		}
	}
	
	/**
	 * Updates the state of the specified tracepoints
	 * 
	 * @param request the request with tracepoint state updates
	 * @param reset if all existing tracepoint state should be reset
	 * @return update result status
	 */
	public RjsStatus updateTracepointStates(final TracepointStatesUpdate request) {
		synchronized (this.stateUpdate) {
			final List<String> reset;
			if (request.getReset()) {
				synchronized (this.pathMap) {
					reset= new ArrayList<>(this.pathMap.keySet());
				}
			}
			else {
				reset= null;
			}
			
			boolean isAnyEnabled= false;
			
			final List<StateEntry> oldStateEntries= new ArrayList<>();
			final List<TracepointState> list= request.getStates();
			for (int i= 0; i < list.size(); ) {
				final String path= list.get(i).getFilePath();
				if (path == null) {
					i++;
					continue;
				}
				
				final PathEntry pathEntry= ensurePathEntry(path);
				synchronized (pathEntry.states) {
					if (reset != null && reset.remove(path) && !pathEntry.states.isEmpty()) {
						oldStateEntries.addAll(pathEntry.states);
						pathEntry.states.clear();
					}
					for (; i < list.size(); i++) {
						final TracepointState state= list.get(i);
						if (!path.equals(state.getFilePath())) {
							break;
						}
						
						final int idx= pathEntry.states.indexOfId(state.getId());
						StateEntry entry= null;
						if (idx >= 0) {
							entry= pathEntry.states.get(idx);
						}
						
						if (state.getType() != Tracepoint.TYPE_DELETED) {
							if (entry == null && reset != null) {
								final int oldIdx= indexOfStateEntry(oldStateEntries, state.getId());
								if (oldIdx >= 0) {
									entry= oldStateEntries.remove(oldIdx);
								}
							}
							if (entry == null) {
								entry= new StateEntry(path, state.getId());
							}
							entry.setState(state);
							if (idx < 0) {
								pathEntry.states.add(entry);
							}
							isAnyEnabled |= state.isEnabled();
						}
						else if (idx >= 0) {
							pathEntry.states.remove(idx);
							oldStateEntries.add(entry);
						}
					}
				}
				
				onRemoved(oldStateEntries);
				oldStateEntries.clear();
				
				if (reset != null) {
					this.isAnyEnabled= isAnyEnabled;
				}
			}
			if (reset != null) {
				for (final String path : reset) {
					final PathEntry entry= ensurePathEntry(path);
					if (!entry.states.isEmpty()) {
						synchronized (entry.states) {
							onRemoved(entry.states);
							entry.states.clear();
						}
					}
				}
			}
			return RjsStatus.OK_STATUS;
		}
	}
	
	private void onRemoved(final List<StateEntry> entries) {
		for (final StateEntry entry : entries) {
			entry.removed();
		}
	}
	
	
	/**
	 * Sets global enablement of breakpoints.
	 * 
	 * @param enabled
	 */
	public void setBreakpointsEnabled(final boolean enabled) {
		this.isBreakpointsEnabled= enabled;
	}
	
	/**
	 * Returns global enablement of breakpoints.
	 * 
	 * @return
	 */
	public final boolean isBreakpointsEnabled() {
		return this.isBreakpointsEnabled;
	}
	
	
	/**
	 * Registers the environment for tracepoint management.
	 * 
	 * @param key
	 * @param envHandle handle of the environment
	 * @param objectNames object names to update
	 */
	public void registerEnv(String key, final Handle envHandle,
			final @Nullable List<String> objectNames) {
		key= key.intern();
		this.envTags.add(key);
		final RhEnv env= this.objManager.registerEnv(envHandle, key);
		updateInst(env, objectNames);
		finishUpdatingInst();
	}
	
	/**
	 * Deletes registration of the environment for tracepoint management.
	 * 
	 * @param key
	 * @param envHandle handle of the environment
	 */
	public void unregisterEnv(final String key, final Handle envHandle) {
		this.objManager.unregisterEnv(envHandle, key.intern());
	}
	
	/**
	 * Deletes registration of the environment for tracepoint management.
	 */
	public void unregisterEnvs(final String key) {
		this.objManager.unregisterEnvs(key.intern());
	}
	
	protected void addEnvWithParents(final List<RhEnv> envs, final RhEnv env) throws RjsException {
		RhEnv env0= env;
		while (env0 != null && !envs.contains(env0)) {
			envs.add(env0);
			
			env0= this.objManager.getParentEnv(env0);
		}
	}
	
	
	public RjsStatus installTracepoints(final ElementTracepointInstallationRequest request)
			throws RjsException {
		final List<? extends ElementTracepoints> tracepointsList= request.getRequests();
		
		addTracepoints(tracepointsList);
		
		if (containsCommonElement(tracepointsList)) {
			updateInst();
		}
		
		return RjsStatus.OK_STATUS;
	}
	
	public RjsStatus installTracepoints(final FlagTracepointInstallationRequest request)
			throws RjsException {
		final byte[] types= request.getTypes();
		final int[] flags= request.getFlags();
		
		for (int i= 0; i < types.length; i++) {
			switch (types[i]) {
			case Tracepoint.TYPE_EB:
				performUpdatingInstEB(flags[i]);
				break;
			default:
				break;
			}
		}
		
		return RjsStatus.OK_STATUS;
	}
	
	public void updateInst() throws RjsException {
		try {
			this.objManager.update();
			final List<RhEnv> envs= new ArrayList<>(64);
			envs.addAll(this.objManager.getSearchPath());
			for (final RhEnv env : this.objManager.getStackFrames()) {
				addEnvWithParents(envs, env);
			}
			for (final RhEnv env: this.objManager.getEnvs()) {
				if ((env.isReg(ENV_INSTALLED_TAG) || env.isRegAny(this.envTags))
						&& !envs.contains(env) ) {
					envs.add(env);
				}
			}
			
			for (final RhEnv env : envs) {
				performUpdatingInst(env, null);
			}
		}
		finally {
			finishUpdatingInst();
		}
	}
	
	public void updateInst(final RhEnv env, final @Nullable List<String> objectNames) {
		try {
			performUpdatingInst(env, objectNames);
		}
		finally {
			finishUpdatingInst();
		}
	}
	
	
	protected abstract void performUpdatingInstEB(final int i);
	
	protected abstract void performUpdatingInst(final RhEnv env, final @Nullable List<String> objectNames);
	
	
	protected void notifyListeners(final List<TracepointEvent> events) {
		if (!events.isEmpty()) {
			this.listener.handle(events);
		}
	}
	
	protected void notifyListeners(final TracepointEvent event) {
		this.listener.handle(ImCollections.newList(event));
	}
	
	protected void beginUpdatingInstEnv(final RhEnv env, final @Nullable List<String> namesToUpdate) {
		this.updatingEnv= env;
		this.updatingEnvComplete= (namesToUpdate == null);
		
		if (LOGGER.isLoggable(Level.FINE)) {
			if (namesToUpdate != null) {
				LOGGER.log(Level.FINE,
						"[TP] Updating element tracpoints in selected element(s) of {0}..." +
								"\n\telementNames= {1}",
						new Object[] { env, namesToUpdate } ); // TODO encode names
			}
			else {
				LOGGER.log(Level.FINE,
						"[TP] Updating element tracpoints in all elements of {0}...",
						new Object[] { env } );
			}
		}
	}
	
	protected final boolean getClearUpdatingInst() {
		return this.updatingEnvComplete;
	}
	
	protected void finishUpdatingInstEnv() {
		final RhEnv env= this.updatingEnv;
		if (env != null) {
			try {
				final boolean clear= this.updatingEnvComplete;
				final StateSet prevInstalled= (StateSet) env.getData(ENV_INSTALLED_TAG);
				final StateSet installed= (clear || prevInstalled == null) ?
						new StateSet(0) : prevInstalled;
				
				final List<PathEntry> pathEntries= getPathEntries();
				for (final PathEntry entry : pathEntries) {
					entry.finishUpdatingInst(env, clear, installed, this.updatingStates);
				}
				
				if (!installed.isEmpty()) {
					if (installed != prevInstalled) {
						env.addReg(ENV_INSTALLED_TAG, installed);
					}
				}
				else {
					if (prevInstalled != null) {
						env.removeReg(ENV_INSTALLED_TAG);
					}
				}
			}
			catch (final Exception e) {
				final LogRecord record= new LogRecord(Level.SEVERE,
						"[TP] An error occured when updating tracepoint installation states for {0}." );
				record.setParameters(new Object[] { env });
				record.setThrown(e);
				LOGGER.log(record);
			}
			finally {
				this.updatingEnv= null;
			}
		}
	}
	
	protected void finishUpdatingInst() {
		if (!this.updatingStates.isEmpty()) {
			final List<TracepointEvent> events= new ArrayList<>();
			for (final StateEntry entry : this.updatingStates) {
				entry.finishUpdatingInst(events);
			}
			
			notifyListeners(events);
			
			this.updatingStates.clear();
		}
	}
	
	protected void updateInstOnRemoved(final RhEnv env) {
		final StateSet installed= ObjectUtils.nonNullAssert(
				(StateSet) env.getData(ENV_INSTALLED_TAG) );
		final List<TracepointEvent> events= new ArrayList<>();
		for (final StateEntry stateEntry : installed) {
			stateEntry.removeInst(env, events);
		}
		
		notifyListeners(events);
	}
	
}