tikhomirov@220: /*
tikhomirov@220:  * Copyright (c) 2011 TMate Software Ltd
tikhomirov@220:  *  
tikhomirov@220:  * This program is free software; you can redistribute it and/or modify
tikhomirov@220:  * it under the terms of the GNU General Public License as published by
tikhomirov@220:  * the Free Software Foundation; version 2 of the License.
tikhomirov@220:  *
tikhomirov@220:  * This program is distributed in the hope that it will be useful,
tikhomirov@220:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@220:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@220:  * GNU General Public License for more details.
tikhomirov@220:  *
tikhomirov@220:  * For information on how to redistribute this software under
tikhomirov@220:  * the terms of a license other than GNU General Public License
tikhomirov@220:  * contact TMate Software at support@hg4j.com
tikhomirov@220:  */
tikhomirov@220: package org.tmatesoft.hg.repo;
tikhomirov@220: 
tikhomirov@236: import java.io.BufferedReader;
tikhomirov@244: import java.io.BufferedWriter;
tikhomirov@236: import java.io.File;
tikhomirov@236: import java.io.FileReader;
tikhomirov@244: import java.io.FileWriter;
tikhomirov@236: import java.io.IOException;
tikhomirov@220: import java.util.Arrays;
tikhomirov@220: import java.util.Collections;
tikhomirov@220: import java.util.HashMap;
tikhomirov@308: import java.util.LinkedHashMap;
tikhomirov@236: import java.util.LinkedHashSet;
tikhomirov@220: import java.util.LinkedList;
tikhomirov@220: import java.util.List;
tikhomirov@220: import java.util.Map;
tikhomirov@220: import java.util.TreeMap;
tikhomirov@236: import java.util.regex.Pattern;
tikhomirov@220: 
tikhomirov@220: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@244: import org.tmatesoft.hg.internal.Experimental;
tikhomirov@220: import org.tmatesoft.hg.repo.HgChangelog.RawChangeset;
tikhomirov@220: import org.tmatesoft.hg.util.ProgressSupport;
tikhomirov@220: 
tikhomirov@220: /**
tikhomirov@220:  *
tikhomirov@220:  * @author Artem Tikhomirov
tikhomirov@220:  * @author TMate Software Ltd.
tikhomirov@220:  */
tikhomirov@220: public class HgBranches {
tikhomirov@220: 	
tikhomirov@220: 	private final Map<String, BranchInfo> branches = new TreeMap<String, BranchInfo>();
tikhomirov@220: 	private final HgRepository repo;
tikhomirov@244: 	private boolean isCacheActual = false;
tikhomirov@244: 
tikhomirov@220: 	HgBranches(HgRepository hgRepo) {
tikhomirov@220: 		repo = hgRepo;
tikhomirov@220: 	}
tikhomirov@220: 
tikhomirov@236: 	private int readCache() {
tikhomirov@244: 		File branchheadsCache = getCacheFile();
tikhomirov@236: 		int lastInCache = -1;
tikhomirov@236: 		if (!branchheadsCache.canRead()) {
tikhomirov@236: 			return lastInCache;
tikhomirov@236: 		}
tikhomirov@236: 		BufferedReader br = null;
tikhomirov@236: 		final Pattern spacePattern = Pattern.compile(" ");
tikhomirov@236: 		try {
tikhomirov@308: 			final LinkedHashMap<String, List<Nodeid>> branchHeads = new LinkedHashMap<String, List<Nodeid>>();
tikhomirov@236: 			br = new BufferedReader(new FileReader(branchheadsCache));
tikhomirov@236: 			String line = br.readLine();
tikhomirov@236: 			if (line == null || line.trim().length() == 0) {
tikhomirov@236: 				return lastInCache;
tikhomirov@236: 			}
tikhomirov@236: 			String[] cacheIdentity = spacePattern.split(line.trim());
tikhomirov@236: 			lastInCache = Integer.parseInt(cacheIdentity[1]);
tikhomirov@236: 			// XXX may want to check if nodeid of cset from repo.getChangelog() of lastInCache index match cacheIdentity[0]
tikhomirov@236: 			//
tikhomirov@236: 			while ((line = br.readLine()) != null) {
tikhomirov@244: 				String[] elements = spacePattern.split(line.trim());
tikhomirov@308: 				if (elements.length != 2) {
tikhomirov@236: 					// bad entry
tikhomirov@236: 					continue;
tikhomirov@236: 				}
tikhomirov@236: 				// I assume split returns substrings of the original string, hence copy of a branch name
tikhomirov@236: 				String branchName = new String(elements[elements.length-1]);
tikhomirov@308: 				List<Nodeid> heads = branchHeads.get(elements[1]);
tikhomirov@308: 				if (heads == null) {
tikhomirov@308: 					branchHeads.put(branchName, heads = new LinkedList<Nodeid>());
tikhomirov@308: 				}
tikhomirov@308: 				heads.add(Nodeid.fromAscii(elements[0]));
tikhomirov@308: 			}
tikhomirov@308: 			for (Map.Entry<String, List<Nodeid>> e : branchHeads.entrySet()) {
tikhomirov@308: 				Nodeid[] heads = e.getValue().toArray(new Nodeid[e.getValue().size()]);
tikhomirov@308: 				BranchInfo bi = new BranchInfo(e.getKey(), heads);
tikhomirov@308: 				branches.put(e.getKey(), bi);
tikhomirov@236: 			}
tikhomirov@236: 			return lastInCache;
tikhomirov@236: 		} catch (IOException ex) {
tikhomirov@295: 			repo.getContext().getLog().warn(getClass(), ex, null); // log error, but otherwise do nothing
tikhomirov@236: 		} finally {
tikhomirov@236: 			if (br != null) {
tikhomirov@236: 				try {
tikhomirov@236: 					br.close();
tikhomirov@236: 				} catch (IOException ex) {
tikhomirov@295: 					repo.getContext().getLog().info(getClass(), ex, null); // ignore
tikhomirov@236: 				}
tikhomirov@236: 			}
tikhomirov@236: 		}
tikhomirov@236: 		return -1; // deliberately not lastInCache, to avoid anything but -1 when 1st line was read and there's error is in lines 2..end
tikhomirov@236: 	}
tikhomirov@236: 
tikhomirov@220: 	void collect(final ProgressSupport ps) {
tikhomirov@236: 		branches.clear();
tikhomirov@220: 		ps.start(1 + repo.getChangelog().getRevisionCount() * 2);
tikhomirov@236: 		//
tikhomirov@236: 		int lastCached = readCache();
tikhomirov@236: 		/*
tikhomirov@236: 		 * Next code was supposed to fill missing aspects of the BranchInfo, but is too slow
tikhomirov@236: 		 * 
tikhomirov@236: 		if (lastCached != -1 && lastCached <= repo.getChangelog().getLastRevision()) {
tikhomirov@236: 			LinkedList<BranchInfo> incompleteBranches = new LinkedList<HgBranches.BranchInfo>(branches.values());
tikhomirov@236: 			for (BranchInfo bi : incompleteBranches) {
tikhomirov@236: 				LinkedList<Nodeid> closedHeads = new LinkedList<Nodeid>();
tikhomirov@236: 				for (Nodeid h : bi.getHeads()) {
tikhomirov@236: 					if ("1".equals(repo.getChangelog().changeset(h).extras().get("close"))) {
tikhomirov@236: 						closedHeads.add(h);
tikhomirov@220: 					}
tikhomirov@220: 				}
tikhomirov@236: 				HashSet<Nodeid> earliest = new HashSet<Nodeid>(bi.getHeads());
tikhomirov@236: 				HashSet<Nodeid> visited = new HashSet<Nodeid>();
tikhomirov@236: 				ArrayList<Nodeid> parents = new ArrayList<Nodeid>(2);
tikhomirov@236: 				HashSet<Nodeid> candidate = new HashSet<Nodeid>();
tikhomirov@236: 				do {
tikhomirov@236: 					candidate.clear();
tikhomirov@236: 					for (Nodeid e : earliest) {
tikhomirov@236: 						parents.clear();
tikhomirov@236: 						if (pw.appendParentsOf(e, parents)) {
tikhomirov@236: 							// at least one parent
tikhomirov@236: 							Nodeid p1 = parents.get(0);
tikhomirov@236: 							if (p1 != null && !visited.contains(p1) && bi.getName().equals(repo.getChangelog().changeset(p1).branch())) {
tikhomirov@236: 								visited.add(p1);
tikhomirov@236: 								candidate.add(p1);
tikhomirov@236: 							}
tikhomirov@236: 							Nodeid p2 = parents.size() > 1 ? parents.get(1) : null;
tikhomirov@236: 							if (p2 != null && !visited.contains(p2) && bi.getName().equals(repo.getChangelog().changeset(p2).branch())) {
tikhomirov@236: 								visited.add(p2);
tikhomirov@236: 								candidate.add(p2);
tikhomirov@236: 							}
tikhomirov@236: 						}
tikhomirov@236: 					}
tikhomirov@236: 					if (!candidate.isEmpty()) {
tikhomirov@236: 						earliest.clear();
tikhomirov@236: 						earliest.addAll(candidate);
tikhomirov@236: 					}
tikhomirov@236: 				} while (!candidate.isEmpty());
tikhomirov@236: 				// earliest can't be empty, we've started with non-empty heads.
tikhomirov@236: 				Nodeid first = null;
tikhomirov@236: 				if (earliest.size() == 1) {
tikhomirov@236: 					first = earliest.iterator().next();
tikhomirov@236: 				} else {
tikhomirov@236: 					int earliestRevNum = Integer.MAX_VALUE;
tikhomirov@236: 					for (Nodeid e : earliest) {
tikhomirov@236: 						int x = repo.getChangelog().getLocalRevision(e);
tikhomirov@236: 						if (x < earliestRevNum) {
tikhomirov@236: 							earliestRevNum = x;
tikhomirov@236: 							first = e;
tikhomirov@236: 						}
tikhomirov@236: 					}
tikhomirov@236: 				}
tikhomirov@236: 				assert first != null;
tikhomirov@236: 				System.out.println("Updated branch " + bi.getName());
tikhomirov@236: 				branches.put(bi.getName(), new BranchInfo(bi.getName(), first, bi.getHeads().toArray(new Nodeid[0]), closedHeads.size() == bi.getHeads().size()));
tikhomirov@220: 			}
tikhomirov@220: 		}
tikhomirov@236: 		*/
tikhomirov@244: 		isCacheActual = lastCached == repo.getChangelog().getLastRevision();
tikhomirov@244: 		if (!isCacheActual) {
tikhomirov@236: 			final HgChangelog.ParentWalker pw = repo.getChangelog().new ParentWalker();
tikhomirov@236: 			pw.init();
tikhomirov@236: 			ps.worked(repo.getChangelog().getRevisionCount());
tikhomirov@308: 			// first revision branch found at
tikhomirov@236: 			final HashMap<String, Nodeid> branchStart = new HashMap<String, Nodeid>();
tikhomirov@308: 			// last revision seen for the branch
tikhomirov@236: 			final HashMap<String, Nodeid> branchLastSeen = new HashMap<String, Nodeid>();
tikhomirov@308: 			// revisions from the branch that have no children at all
tikhomirov@236: 			final HashMap<String, List<Nodeid>> branchHeads = new HashMap<String, List<Nodeid>>();
tikhomirov@309: 			// revisions that are immediate children of a node from a given branch
tikhomirov@309: 			// after iteration, there are some revisions left in this map (children of a branch last revision
tikhomirov@309: 			// that doesn't belong to the branch. No use of this now, perhaps can deduce isInactive (e.g.those 
tikhomirov@309: 			// branches that have non-empty candidates are inactive if all their heads are roots for those left)
tikhomirov@308: 			final HashMap<String, List<Nodeid>> branchHeadCandidates = new HashMap<String, List<Nodeid>>();
tikhomirov@236: 			HgChangelog.Inspector insp = new HgChangelog.Inspector() {
tikhomirov@236: 				
tikhomirov@236: 				public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) {
tikhomirov@236: 					String branchName = cset.branch();
tikhomirov@236: 					if (!branchStart.containsKey(branchName)) {
tikhomirov@236: 						branchStart.put(branchName, nodeid);
tikhomirov@236: 						branchHeads.put(branchName, new LinkedList<Nodeid>());
tikhomirov@308: 						branchHeadCandidates.put(branchName, new LinkedList<Nodeid>());
tikhomirov@236: 					} else {
tikhomirov@308: 						final List<Nodeid> headCandidates = branchHeadCandidates.get(branchName);
tikhomirov@308: 						if (headCandidates.remove(nodeid)) {
tikhomirov@309: 							// likely we don't need to keep parent anymore, as we found at least 1 child thereof to be at the same branch
tikhomirov@309: 							// however, it's possible the child we found is a result of an earlier fork, and revision in the 
tikhomirov@309: 							// branchLastSeen is 'parallel' head, which needs to be kept
tikhomirov@309: 							Nodeid lastSeenInBranch = branchLastSeen.get(branchName);
tikhomirov@309: 							// check if current revision is on descendant line. Seems direct parents check is enough
tikhomirov@309: 							if (pw.safeFirstParent(nodeid).equals(lastSeenInBranch) || pw.safeSecondParent(nodeid).equals(lastSeenInBranch)) {
tikhomirov@309: 								branchLastSeen.remove(branchName);
tikhomirov@309: 							}
tikhomirov@236: 						}
tikhomirov@236: 					}
tikhomirov@308: 					List<Nodeid> immediateChildren = pw.directChildren(nodeid);
tikhomirov@308: 					if (immediateChildren.size() > 0) {
tikhomirov@308: 						// 1) children may be in another branch
tikhomirov@308: 						// and unless we later came across another element from this branch,
tikhomirov@308: 						// we need to record all these as potential heads
tikhomirov@308: 						//
tikhomirov@308: 						// 2) head1 with children in different branch, and head2 in this branch without children
tikhomirov@308: 						branchLastSeen.put(branchName, nodeid);
tikhomirov@308: 						branchHeadCandidates.get(branchName).addAll(immediateChildren);
tikhomirov@308: 					} else {
tikhomirov@308: 						// no more children known for this node, it's (one of the) head of the branch
tikhomirov@308: 						branchHeads.get(branchName).add(nodeid);
tikhomirov@308: 					}
tikhomirov@236: 					ps.worked(1);
tikhomirov@236: 				}
tikhomirov@236: 			}; 
tikhomirov@236: 			repo.getChangelog().range(lastCached == -1 ? 0 : lastCached+1, HgRepository.TIP, insp);
tikhomirov@308: 			// those last seen revisions from the branch that had no children from the same branch are heads.
tikhomirov@236: 			for (String bn : branchLastSeen.keySet()) {
tikhomirov@308: 				// these are inactive branches? - there were children, but not from the same branch?
tikhomirov@236: 				branchHeads.get(bn).add(branchLastSeen.get(bn));
tikhomirov@236: 			}
tikhomirov@236: 			for (String bn : branchStart.keySet()) {
tikhomirov@236: 				BranchInfo bi = branches.get(bn);
tikhomirov@236: 				if (bi != null) {
tikhomirov@236: 					// although heads from cache shall not intersect with heads after lastCached,
tikhomirov@236: 					// use of LHS doesn't hurt (and makes sense e.g. if cache is not completely correct in my tests) 
tikhomirov@236: 					LinkedHashSet<Nodeid> heads = new LinkedHashSet<Nodeid>(bi.getHeads());
tikhomirov@236: 					for (Nodeid oldHead : bi.getHeads()) {
tikhomirov@236: 						// XXX perhaps, need pw.canReach(Nodeid from, Collection<Nodeid> to)
tikhomirov@236: 						List<Nodeid> newChildren = pw.childrenOf(Collections.singletonList(oldHead));
tikhomirov@236: 						if (!newChildren.isEmpty()) {
tikhomirov@236: 							// likely not a head any longer,
tikhomirov@236: 							// check if any new head can be reached from old one, and, if yes,
tikhomirov@236: 							// do not consider that old head as head.
tikhomirov@236: 							for (Nodeid newHead : branchHeads.get(bn)) {
tikhomirov@236: 								if (newChildren.contains(newHead)) {
tikhomirov@236: 									heads.remove(oldHead);
tikhomirov@236: 									break;
tikhomirov@236: 								}
tikhomirov@236: 							}
tikhomirov@236: 						} // else - oldHead still head for the branch
tikhomirov@236: 					}
tikhomirov@236: 					heads.addAll(branchHeads.get(bn));
tikhomirov@308: 					bi = new BranchInfo(bn, bi.getStart(), heads.toArray(new Nodeid[0]));
tikhomirov@236: 				} else {
tikhomirov@236: 					Nodeid[] heads = branchHeads.get(bn).toArray(new Nodeid[0]);
tikhomirov@308: 					bi = new BranchInfo(bn, branchStart.get(bn), heads);
tikhomirov@236: 				}
tikhomirov@236: 				branches.put(bn, bi);
tikhomirov@236: 			}
tikhomirov@220: 		}
tikhomirov@308: 		final HgChangelog clog = repo.getChangelog();
tikhomirov@308: 		final HgChangelog.RevisionMap rmap = clog.new RevisionMap().init();
tikhomirov@308: 		for (BranchInfo bi : branches.values()) {
tikhomirov@308: 			bi.validate(clog, rmap);
tikhomirov@308: 		}
tikhomirov@220: 		ps.done();
tikhomirov@220: 	}
tikhomirov@220: 
tikhomirov@220: 	public List<BranchInfo> getAllBranches() {
tikhomirov@220: 		return new LinkedList<BranchInfo>(branches.values());
tikhomirov@220: 				
tikhomirov@220: 	}
tikhomirov@220: 
tikhomirov@220: 	public BranchInfo getBranch(String name) {
tikhomirov@220: 		return branches.get(name);
tikhomirov@220: 	}
tikhomirov@244: 
tikhomirov@244: 	/**
tikhomirov@244: 	 * Writes down information about repository branches in a format Mercurial native client can understand.
tikhomirov@244: 	 * Cache file gets overwritten only if it is out of date (i.e. misses some branch information)
tikhomirov@244: 	 */
tikhomirov@244: 	@Experimental(reason="Usage of cache isn't supposed to be public knowledge")
tikhomirov@244: 	public void writeCache() {
tikhomirov@244: 		if (isCacheActual) {
tikhomirov@244: 			return;
tikhomirov@244: 		}
tikhomirov@244: 		try {
tikhomirov@244: 			File branchheadsCache = getCacheFile();
tikhomirov@244: 			if (!branchheadsCache.exists()) {
tikhomirov@244: 				branchheadsCache.getParentFile().mkdirs(); // just in case cache/ doesn't exist jet
tikhomirov@244: 				branchheadsCache.createNewFile();
tikhomirov@244: 			}
tikhomirov@244: 			if (!branchheadsCache.canWrite()) {
tikhomirov@244: 				return;
tikhomirov@244: 			}
tikhomirov@244: 			final int lastRev = repo.getChangelog().getLastRevision();
tikhomirov@244: 			final Nodeid lastNid = repo.getChangelog().getRevision(lastRev);
tikhomirov@244: 			BufferedWriter bw = new BufferedWriter(new FileWriter(branchheadsCache));
tikhomirov@244: 			bw.write(lastNid.toString());
tikhomirov@244: 			bw.write((int) ' ');
tikhomirov@244: 			bw.write(Integer.toString(lastRev));
tikhomirov@244: 			bw.write("\n");
tikhomirov@244: 			for (BranchInfo bi : branches.values()) {
tikhomirov@244: 				for (Nodeid nid : bi.getHeads()) {
tikhomirov@244: 					bw.write(nid.toString());
tikhomirov@244: 					bw.write((int) ' ');
tikhomirov@244: 					bw.write(bi.getName());
tikhomirov@244: 					bw.write("\n");
tikhomirov@244: 				}
tikhomirov@244: 			}
tikhomirov@244: 			bw.close();
tikhomirov@295: 		} catch (IOException ex) {
tikhomirov@295: 			repo.getContext().getLog().error(getClass(), ex, "Error writing branch cache file");
tikhomirov@244: 		}
tikhomirov@244: 	}
tikhomirov@244: 
tikhomirov@244: 	private File getCacheFile() {
tikhomirov@244: 		// prior to 1.8 used to be .hg/branchheads.cache
tikhomirov@244: 		return new File(repo.getRepositoryRoot(), "cache/branchheads");
tikhomirov@244: 	}
tikhomirov@244: 
tikhomirov@220: 	public static class BranchInfo {
tikhomirov@220: 		private final String name;
tikhomirov@308: 		private List<Nodeid> heads;
tikhomirov@308: 		private boolean closed;
tikhomirov@220: 		private final Nodeid start;
tikhomirov@220: 
tikhomirov@236: 		// XXX in fact, few but not all branchHeads might be closed, and isClosed for whole branch is not
tikhomirov@236: 		// possible to determine.
tikhomirov@308: 		BranchInfo(String branchName, Nodeid first, Nodeid[] branchHeads) {
tikhomirov@220: 			name = branchName;
tikhomirov@220: 			start = first;
tikhomirov@308: 			heads = Arrays.asList(branchHeads);
tikhomirov@220: 		}
tikhomirov@236: 		
tikhomirov@236: 		// incomplete branch, there's not enough information at the time of creation. shall be replaced with
tikhomirov@236: 		// proper BI in #collect()
tikhomirov@236: 		BranchInfo(String branchName, Nodeid[] branchHeads) {
tikhomirov@308: 			this(branchName, Nodeid.NULL, branchHeads);
tikhomirov@308: 		}
tikhomirov@308: 		
tikhomirov@308: 		void validate(HgChangelog clog, HgChangelog.RevisionMap rmap) {
tikhomirov@308: 			int[] localCset = new int[heads.size()];
tikhomirov@308: 			int i = 0;
tikhomirov@308: 			for (Nodeid h : heads) {
tikhomirov@308: 				localCset[i++] = rmap.localRevision(h);
tikhomirov@308: 			}
tikhomirov@308: 			// [0] tipmost, [1] tipmost open
tikhomirov@308: 			final Nodeid[] tipmost = new Nodeid[] {null, null};
tikhomirov@308: 			final boolean[] allClosed = new boolean[] { true };
tikhomirov@308: 			clog.range(new HgChangelog.Inspector() {
tikhomirov@308: 				
tikhomirov@308: 				public void next(int revisionNumber, Nodeid nodeid, RawChangeset cset) {
tikhomirov@308: 					assert heads.contains(nodeid);
tikhomirov@308: 					tipmost[0] = nodeid;
tikhomirov@308: 					if (!"1".equals(cset.extras().get("close"))) {
tikhomirov@308: 						tipmost[1] = nodeid;
tikhomirov@308: 						allClosed[0] = false;
tikhomirov@308: 					}
tikhomirov@308: 				}
tikhomirov@308: 			}, localCset);
tikhomirov@308: 			closed = allClosed[0];
tikhomirov@308: 			Nodeid[] outcome = new Nodeid[localCset.length];
tikhomirov@308: 			i = 0;
tikhomirov@308: 			if (!closed && tipmost[1] != null) { 
tikhomirov@308: 				outcome[i++] = tipmost[1];
tikhomirov@308: 				if (i < outcome.length && !tipmost[0].equals(tipmost[1])) {
tikhomirov@308: 					outcome[i++] = tipmost[0];
tikhomirov@308: 				}
tikhomirov@308: 			} else {
tikhomirov@308: 				outcome[i++] = tipmost[0];
tikhomirov@308: 			}
tikhomirov@308: 			for (Nodeid h : heads) {
tikhomirov@308: 				if (!h.equals(tipmost[0]) && !h.equals(tipmost[1])) {
tikhomirov@308: 					outcome[i++] = h;
tikhomirov@308: 				}
tikhomirov@308: 			}
tikhomirov@308: 			heads = Arrays.asList(outcome);
tikhomirov@236: 		}
tikhomirov@220: 
tikhomirov@220: 		public String getName() {
tikhomirov@220: 			return name;
tikhomirov@220: 		}
tikhomirov@308: 		/**
tikhomirov@308: 		 * @return <code>true</code> if all heads of this branch are marked as closed
tikhomirov@308: 		 */
tikhomirov@308: 		public boolean isClosed() {
tikhomirov@220: 			return closed;
tikhomirov@220: 		}
tikhomirov@220: 		public List<Nodeid> getHeads() {
tikhomirov@220: 			return heads;
tikhomirov@220: 		}
tikhomirov@220: //		public Nodeid getTip() {
tikhomirov@220: //		}
tikhomirov@236: 		/*public*/ Nodeid getStart() {
tikhomirov@220: 			// first node where branch appears
tikhomirov@220: 			return start;
tikhomirov@220: 		}
tikhomirov@220: 	}
tikhomirov@220: }