mapjoin.cc #1

/*
 * Copyright 1995, 1996 Perforce Software.  All rights reserved.
 *
 * This file is part of Perforce - the FAST SCM System.
 */

//
// mapping.cc - the mapping master
//

# include <stdhdrs.h>
# include <error.h>
# include <strbuf.h>
# include <vararray.h>

# include <debug.h>
# include <tunable.h>

# include <msgdb.h>

# include "maphalf.h"
# include "maptable.h"
# include "mapstring.h"
# include "mapdebug.h"
# include "mapitem.h"

/*
 * mapFlagGrid -- how to combine two mapFlags
 */

MapFlag mapFlagGrid[4][4] = {

		/* Map */	/* Unmap */	/* Remap */	/* Havemap */
/* Map */	MfMap,		MfUnmap,	MfRemap,	MfHavemap,
/* Unmap */	MfUnmap,	MfUnmap,	MfUnmap,	MfUnmap,
/* Remap */	MfRemap,	MfUnmap,	MfRemap,	MfHavemap,
/* Havemap */	MfHavemap,	MfUnmap,	MfHavemap,	MfHavemap,

} ;

class MapJoiner : public Joiner {

    public:

	MapJoiner()
	{
	    badJoin = 0;
	    m0 = new MapTable;
	}

	virtual	void Insert()
	{
	    map->Lhs()->Expand( *this, newLhs, params );
	    map->Rhs()->Expand( *this, newRhs, params );
	    MapFlag mapFlag = mapFlagGrid[ map->Flag() ][ map2->Flag() ];
	    m0->InsertNoDups( newLhs, newRhs, mapFlag );
	}

    public:
	MapTable *m0;

	MapItem *map;
	MapItem *map2;

    protected:
	StrBuf newLhs;
	StrBuf newRhs;
} ;

class MapJoiner2 : public MapJoiner {

    public:
	MapTableT dir1;
	MapTableT dir2;

	MapJoiner2( MapTableT dir1, MapTableT dir2 )
	{
	    this->dir1 = dir1;
	    this->dir2 = dir2;
	}

	virtual	void Insert()
	{
	    map->Ohs( dir1 )->Expand( *this, newLhs, params );
	    map2->Ohs( dir2 )->Expand( *this, newRhs, params2 );
	    MapFlag mapFlag = mapFlagGrid[ map->Flag() ][ map2->Flag() ];
	    m0->InsertNoDups( newLhs, newRhs, mapFlag );
	}
} ;

void
MapTable::JoinOptimizer( MapTableT dir2 )
{
	if( !trees[ dir2 ].tree )
	    MakeTree( dir2 );
}

void
MapTable::Join( 
	MapTable *m1, MapTableT dir1, 
	MapTable *m2, MapTableT dir2,
	MapJoiner *j, const ErrorId *reason )
{
	if( DEBUG_JOIN )
	{
	    m1->Dump( dir1 == LHS ? "lhs" : "rhs" );
	    m2->Dump( dir2 == LHS ? "lhs" : "rhs" );
	}

	// Give up if we internally produce more than 1,000,000 rows
	// or more than 10000 + the sum of the two mappings.

	// This can happen when joining multiple lines with multiple
	// ...'s on them.

	const int max1 = p4tunable.Get( P4TUNE_MAP_JOINMAX1 );
	const int max2 = p4tunable.Get( P4TUNE_MAP_JOINMAX2 );

	int m = max1 + m1->count + m2->count;
	if( m > max2 ) m = max2;

	if( !m2->trees[ dir2 ].tree )
	{	
	  for(j->map = m1->entry; j->map && count<m; j->map = j->map->Next())
	        for(j->map2 = m2->entry; j->map2; j->map2 = j->map2->Next())
		{
	            j->map->Ths( dir1 )->Join( j->map2->Ths( dir2 ), *j );
		    if( j->badJoin )
		    {
			joinError = 1;
			emptyReason = &MsgDb::TooWild2;
			reason = &MsgDb::TooWild2;
			this->joinError = 1;
			this->emptyReason = &MsgDb::TooWild;
			return;
		    }
		}
	}
	else
	{
	    // Generate a list of possible pairs of maps to join.
	    // These are maps whose non-wild initial substrings match.
	    // We used to just do for()for(), but when joining large
	    // maps that's slow.  So the inner loop is now a tree
	    // search.  

	    MapPairArray pairArray( dir1, dir2 );

	    if( m2->trees[ dir2 ].tree )
	        for( MapItem *i1 = m1->entry; i1 && count < m; i1 = i1->Next() )
	    {
	        // This inserts entries in tree order,
	        // rather than chain order (precedence), so we have to
	        // resort before doing the MapHalf::Join() calls.

	        pairArray.Clear();
	        pairArray.Match( i1, m2->trees[ dir2 ].tree );
	        pairArray.Sort();

	        MapPair *jp;

	        // Walk the list of possible pairs and call MapHalf::Join()
	        // to do the wildcard joining.

	        for( int i = 0; jp = pairArray.Get(i); i++ )
	        {
		    j->map = jp->item1;
		    j->map2 = jp->tree2;
		    jp->h1->Join( jp->h2, *j );
		    delete jp;
	        }
	    }
	}

	// Insert() reverses the order

	this->Reverse();

	// Empty reasons

	if( count >= m )
	{
	    emptyReason = &MsgDb::TooWild;
	    Clear();
	}
	else if( m1->IsEmpty() && m1->emptyReason )
	{
	    emptyReason = m1->emptyReason;
	}
	else if( m2->IsEmpty() && m2->emptyReason )
	{
	    emptyReason = m2->emptyReason;
	}
	else if( !hasMaps && reason )
	{
	    emptyReason = reason;
	}

	if( DEBUG_JOIN )
	    this->Dump( "map joined" );
}

MapTable *
MapTable::Join( 
	MapTableT dir1, 
	MapTable *m2, 
	MapTableT dir2, 
	const ErrorId *reason )
{
	MapJoiner j;
	j.m0->Join( this, dir1, m2, dir2, &j, reason );
	return j.m0;
}

MapTable *
MapTable::Join2( 
	MapTableT dir1, 
	MapTable *m2, 
	MapTableT dir2, 
	const ErrorId *reason )
{
	MapJoiner2 j( dir1, dir2 );
	j.m0->Join( this, dir1, m2, dir2, &j, reason );
	return j.m0;
}

class MapDisambiguate : public MapJoiner {

    public:
	virtual	void Insert()
	{
	    map->Lhs()->Expand( *this, newLhs, params2 );
	    map->Rhs()->Expand( *this, newRhs, params2 );
	    m0->InsertNoDups( newLhs, newRhs, MfUnmap );
	}
} ;

/*
 * MapTable::JoinCheck() - does this maptable include this string?
 *
 * This isn't simply finding if a file is mapped by the table, but
 * rather if a _mapping_ is mapped by the table.  So we have to take
 * the mapping, put it into its own table, join it, and then throw
 * it all away.  Kinda _slow_.
 */

int
MapTable::JoinCheck( MapTableT dir, const StrPtr &lhs )
{
	MapTable c;

	c.Insert( lhs );
	MapTable *j = c.Join( LHS, this, dir );
	int empty = j->IsEmpty(); 
	delete j;

	return !empty;
}

/*
 * MapTable::Disambiguate() - handle un/ambiguous mappings
 *
 *	Mappings provided by the user (client views, branch views)
 *	can be ambiguous since later mappings can override earlier
 *	ones.  Disambiguate() adds explicit exclusion (-) mappings 
 *	for any ambiguous mappings, so that Join() and Translate()
 *	don't have to worry about them.
 *
 *	For example:
 *
 *		a/... b/...
 *		a/c b/d
 *
 *	becomes
 *
 *		a/... b/...
 *		-a/c -b/c
 *		-a/d -b/d
 *		a/c b/d
 *
 *	Unmaps are handled similarly, but the high precedence unmap
 *	line itself is not added, because everything that can be unmapped
 *	has been done so by joining it against the lower precedence
 *	mapping lines:
 *
 *		a/... b/...
 *		-a/c b/d
 *
 *	becomes
 *
 *		a/... b/...
 *		-a/c -b/c
 *		-a/d -b/d
 */

void
MapTable::Disambiguate()
{
	MapDisambiguate j;

	// From high precendence to low precedence

	for( j.map = this->entry; j.map; j.map = j.map->Next() )
	{
	    // We skip unmap lines, because we only need to
	    // unmap to the extent that the unmap lines match lower
	    // precedence map lines.  We do that below.

	    if( j.map->Flag() == MfUnmap )
		continue;

	    // Look for higher precedence mappings that match (join)
	    // this mapping, and to the extent that they overlap add 
	    // unmappings.  We do this for both MfMap and MfUnmap.
	    // A higher precedence MfRemap doesn't occlude us, so
	    // we skip those.

	    // From higher precedence back down to this mapping

	    for( j.map2 = this->entry; 
		 j.map2 != j.map;
		 j.map2 = j.map2->Next() )
	    {
		if( j.map2->Flag() != MfRemap && j.map2->Flag() != MfHavemap )
		{
		    j.map2->Lhs()->Join( j.map->Lhs(), j );
		    j.map2->Rhs()->Join( j.map->Rhs(), j );
		}
	    }

	    // now the original map entry

	    j.m0->Insert( *j.map->Lhs(), *j.map->Rhs(), j.map->Flag() );
	}

	// Inserted order leaves low precedence at the head of the
	// list.  Reverse to get it back where it belongs.

	j.m0->Reverse();

	// Just zonk our own and copy j.m0's

	Clear();
	Insert( j.m0, 1, 0 );
	delete j.m0;
}